Адлемана. Померанца и Рамели [15]. Для доказательства простоты или непростоты числа N этот алгоритм требует (In А)с1п1п1пЛГ арифметических операций. Здесь с - некоторая положительная абсолютная постоянная. Функция lnlnln N хоть и медленно, но всё же возрастает с ростом N. поэтому алгоритм не является полиномиальным. Но всё же его практические реализации позволяют достаточно быстро тестировать числа на простоту. Существенные усовершенствования и упрощения в первоначальный вариант алгоритма были внесены в работах X. Ленстры и А. Коена [16. 17]. Мы будем называть описываемый ниже алгоритм алгоритмом Адлемана - Ленстры.

В основе алгоритма лежит использование сравнений типа малой теоремы Ферма, но в кольцах целых чисел круговых полей, т. е. полей, порождённых над полем Q числами (р = e2mlp - корнями из 1. Пусть q - простое нечётное число и с - первообразный корень по модулю q. т. е. образующий элемент мультипликативной группы поля ¥q. которая пиклична. Для каждого целого числа х, не делящегося на q, можно определить его индекс. indg х 6 Z/(g- 1)Z. называемый также дискретным логарифмом, с помощью сравнения х = cmdqX (mod q). Рассмотрим далее два простых числа р, q с условием, что q - 1 делится на р, но не делится на р2.

Следующая функция, определённая на множестве целых чисел.

0. если q\x, Qp , если (x,q) = 1

является характером по модулю q и порядок этого характера равен р. Сумма

r(x) = -E*W ez[cP!C9]

называется суммой Гаусса. Формулируемая ниже теорема 3 представляет собой аналог малой теоремы Ферма, используемый в алгоритме Адлемана - Ленстры.

Теорема 3. Пусть N - нечётное простое число. (N,pq) = 1. Тогда б кольце Zi[(p.Xq] выполняется сравнение

t(X)n = x(N)-N t(xn) (mod NZ[(P, q).

Если при каких-либо числах р, q сравнение из теоремы 3 нарушается, можно утверждать, что N составное число. В противном случае, если сравнение выполняется, оно даёт некоторую информацию о возможных простых делителях числа N. Собрав такую информацию для различных

p. q. в конце концов удаётся установить, что N имеет лишь один простой делитель и является простым.

В случае р = 2 легко проверить, что сравнение из теоремы 3 равносильно хорошо известному в элементарной теории чисел сравнению

q =(mod N).(13)

где [jJ - так называемый символ Якоби. Хорошо известно также, что последнее сравнение выполняется не только для простых q. но и для любых целых q. взаимно простых с N. Заметим также, что для вычисления символа Якоби существует быстрый алгоритм, основанный на законе взаимности Гаусса и. в некотором смысле, подобный алгоритму Евклида вычисления наибольшего обшего делителя. Следующий пример показывает, каким образом выполнимость нескольких сравнений типа (13) даёт некоторую информацию о возможных простых делителях числа N.

Пример (X. Ленстра). Пусть N - натуральное число. (N.6) = 1, для которого выполнены сравнения

= (jJ (mod N). при а = -1.2,3.(14)

а кроме того с некоторым целым числом Ь имеем

Ь~ = -1 (mod N).(15)

Как уже указывалось, при простом N сравнения (14) выполняются для любого а. взаимно простого с N. а сравнение (15) означает, что Ь есть первообразный корень по модулю N. Количество первообразных корней равно (f(N - 1), т. е. достаточно велико. Таким образом, число Ь с условием (15) при простом N может быть найдено достаточно быстро с помошью случайного выбора и последующей проверки (15).

Докажем, что из выполнимости (14-15) следует, что каждый делитель г числа N удовлетворяет одному из сравнений

г = 1 (mod 24) или г = N (mod 24).(16)

Не уменьшая общности, можно считать, что г - простое число. Введем теперь обозначения N - 1 = и 2k. г - 1 = v 2Ш. где и и v - нечётные числа. Из (15) и сравнения Ъг~1 = 1 (mod г) следует, что m к. Далее, согласно (14), выполняются следующие сравнения \ / \ v/ \ /

а * а *-,nv2k-x / „л \а\а \ - „uv2

означающие (в силу того, что символ Якоби может равняться лишь - 1 или +1), что

NJ ~

При то > к это равенство означает, что -J = 1 при а = -1.2.3. и.

следовательно, г = 1 (mod 24). Если же то = /г. то имеем (jj = - г = N (mod 24). Этим (16) доказано.

Информация такого рода получается и в случае произвольных простых чисел р и q с указанными выше свойствами.

Опишем (очень грубо) схему алгоритма Адлемана - Ленстры для проверки простоты N:

1)выбираются различные простые числа р\,.. .,р\. и различные простые нечётные q\..... qs такие, что

а)для каждого j все простые делители числа qj - 1 содержатся среди pi,... ,рк и qj - 1 не делятся на квадрат простого числа;

б)S = 2gi • ... • qs > л/N.

2)для каждой пары выбранных чисел p. q проводятся тесты, подобные сравнению из теоремы 3. Если N не удовлетворяет какому-либо из этих тестов - оно составное. В противном случае

3)определяется не очень большое множество чисел, с которыми только и могут быть сравнимы простые делители N. А именно, каждый простой делитель г числа N должен удовлетворять сравнению вида

г = N3 (mod S), 0 . j < Т = pi ... pk-

4)проверяется, содержит ли найденное множество делители N. Если при этом делители не обнаружены, утверждается, что N - простое число.

Если число N составное, оно обязательно имеет простой делитель г. меньший y/N < S, который сам содержится среди возможных остатков. Именно на этом свойстве основано применение пункта 4) алгоритма.

Пример. Если выбрать следующие множества простых чисел

{р} = {2,3,5,7} и {q} = {3,7,11,31,43,71,211},

то таким способом удается проверять простоту чисел N < 8,5 • 1019.

Отметим, что в работе [15] для тестирования использовались не сравнения теоремы 3, а закон взаимности для степенных вычетов и так