а = 6 (mod p1), а = 1 (mod p2),

а = 1 (mod pk ) Для этого элемента должно выполняться равенство

По условию для данного элемента должно выполняться сравнение (2), откуда ат=() =-1 (modp2)- Вместе с тем, согласно выбору элемента но быть а = 1 (mod p2 mopeчие. □

Числа те сравнению (2) при а € Z", называются

доказанной выше теоремы получаем, что аналога чисел Кармайкла, которые были бы составными и эйлеровыми псевдопростыми для всех а

Д. Лемером в 1976 г. и Р. Соловеем и В.Штрассеном в 1977 г.

Р. Соловей и В.Штрассен предложили следующий вероятностный тест для проверки простоты чисел:

а {1, 2, , n - 1}

(а, n) = 1

3) проверяем выполнимость сравнения (2);

5) если сравнение выполнено, то ответ неизвестен (и тест можно повторить еще раз).

Сложность данного теста, как и теста на основе малой теоремы Ферма, оценивается величиной O(log3 n).

Данный тест полностью аналогичен тесту на основе малой теоремы Ферма, однако, он обладает решающим преимуществом - при его использовании возникает только две ситуации: n

- число отностью успеха не меньше 1/2 n

1/2k

Доказательство оценки вероятности успеха вытекает из следующе-

(а) если стое по основанию а € Z", то оно

(б) если n жтое по основаниям а, 6 € то n

а6 а6-1

(в) множество

(mod n)

является подгруппой группы Fn = (а € Zn: an 1 = 1 (mod n)};

(г) если n жвдопростым по основанию а

\En\A-\K\. и

Приведем без доказательства еще один результат.

Теорема. Если верна обобщенная гипотеза Римана, то существует константа C>0 то если n является Эйлерово псевдопростым для всех оснований тервала 1 < а < C log2 то n - про-□

11.6. Тест Рабина-Миллера

n n- 1=2st t n

простым, то при всех а тся сравнение an-1 = 1 (mod n).

а , а2 , , а2

что либо среди них найдется равный -1 (mod отбо а* = 1 (mod n).

На этом замечании основан следующий вероятностный тест простоты:

а {1, 2, , n - 1}

(а, n) = 1

а (mod n)

4) если а* = ±1 (mod n), то переходим к п. 1;

5) вычисляем (a)2, (a)4(a* )2s 1 (mod и) до тех пор, пока не -1

-1 и

рить еще раз).

Арифметическая сложность данного теста, очевидно, составляет O(su).

Назовем число тым по основанию a, если выполняется условие:

a* = 1 (mod и) 3r, 0 < r<s, a2* =-1 (mod и). (3)

561 = 3 - 11 - 17 2 561 - 1=16-35

По китайской теореме об остатках число 2 представляется остатками (2, 2, 2)

(-1, -1, -1) -1

числа в колонках ведут себя независимо и случайно, то интуитивно понятно, почему вероятность появления этого события в случае и

Дж. Миллер в 1975 г. доказал, что как и в методе Соловея-Штрас-сена сильно псевдопростых чисел по любому основанию, подобных числам Кармайкла, не существует, и предложил детерминированный вариант приведенного выше теста, когда проверяются все числа ходящие cи0133. Он доказал, что данный тест делает 0(и1/7 еделяет, является ли число и составным или простым. В 1981 г. Л. Эдлеман и Ф. Лэйтон модифицировали алгоритм Миллера и улучшили оценку арифметической сложности до O(и1/1089).

М. Рабин в 1980 г. предложил данный вероятностный вариант теста и доказал, что доля чисел a £ ых число и является псевдопростым по данному основанию, не меньше 3/4. Поэтому после

числа не превосходит 1/4 нка 3/4, по-видимому, неулучшаема,

652969351 = 271 - 811 - 2971 a

для которых данное число является сильно псевдопростым, составляет 0.751 числа 2000436751 = 487 -1531 - 2683, соответственно, 0.7507

Наименьшими сильно псевдопростыми числами являются следующие:

a > 1

Однако, объединяя тесты для нескольких значений баз, можно получить целый ряд интересных тестов, позволяющих проверять простоту маленьких простых чисел: если и < 1 373 653 сильно псев-

2 3 и и < 25 326 001

2 3 5 и

и < 25 000 000 000 2 3 5 7

то либо и = 3 215 031751 тбо и -простое; (Померанц, Селфридж, Вогстаф, 1980) если и < 2 152 302 898 747 сильно псевдопростое по основаниям 2, 3, 5 7 и 1о тое; если и < 3 474749 660383

2 3 5 7 11 13 и и < 341 550 071 728 321 2 3

5 7 11 13 17 и

В заключение приведем без доказательства результат Миллера.

1 <a < 2 log2 то ист ое. □

11.Т. Полиномиальный тест распознавания простоты

Приведем полиномиальный алгоритм распознавания простоты, появившийся в августе 2002 г. и изложенный в предварительном

варианте статьи Manindra Agrawal, Neeraj Kayal, Nitin Saxena. PRIMES is in P (http: www.cse.iitk.ac.in/news/primality.pdf). Алгоритм основан на следующем критерии простоты.

а n n

в том и только в том случае, когда выполнено сравнение

(x - a)n = (xn - а) (mod n)

Доказательство. При О < i < n кщент при xi в выражении ((x - a)n - (xn - а)) шеи ( -1)n)an- му, еели n -простое, то все коэффициенты сравнимы с нулем.

Пусть шиое ид - ст ой делш чи ела n, такой, что n = qkt, (q,t) = гда делит (" то просто с an-q и,

следовательно, коэффициент при xq не сравним с нулем, что и дока-□

При непосредственной проверке этого равенства требуется вычис-n - 2

ниже алгоритме вместо сравнения (1) рассматриваются сравнения (по двум модулям) вида

(x - a)n = (xn - а) (mod xr - 1, mod n),

где значения и r перебираются специальным образом: сначала ищется «подходящее» значение r, а затем для него проверяется сравне-

Приведем сам алгоритм. n > 1

1. if (число ет вид 6 > 1) output «составное»;

r<n 4. begin

(n, r) = 1

7. вычислить q- достой делитель r-1;

8. if (q > 4\/rlogn) и [n~ ф 1 (mod г))

9. break;

10. r r + 1;

11. end r=n

13. for a = 1 to 2\/rlogn

14. if ((x - a)n = (xn - a) (mod xr - 1, mod n))

15. output «составное»;

16. output «простое».

Замечание. Шаг 12 алгоритма внесен в связи с тем, что при малых nr Действительно, из неравенств

--- q 4 л/г log п

получаем г - Sylog п - 1 > 0. Так как положительный корень уравнения ж2 -(81ogn)a; -1=0 имеет вид ж=4 log п+ л/16 log2 п + 1 >8 log п, то r >64 log2 оканчиваться значением r=n толь-

ными.

Проанализируем алгоритм. Сначала покажем, что для завершения первого цикла (while) достаточно выполнить O((log n)6) шагов. Отсюда будет следовать, что во втором цикле (for) надо выполнить 2л/г log n=0((log n)4) шагов, и поэтому алгоритм будет работать полиномиальное число шагов, каждый из которых имеет полиномиальную сложность.

Воспользуемся фундаментальным результатом Е. Фоуври из аналитической теории чисел (см. [24], [32]), который приведем без доказательства.

Лемма. Пусть Р(n) елитель числа n, П1 (x) - число простых чисел p p < щих условию Р(p - 1) > x2/3. Тогда найдутся константа с > О ральное no такие, что для

n > no

7Г1(ж) С--.

log x

а1 а2

натуральное то для всех n > тервале [а1 (log n)6, a2(log n)6 щостое число r ж, что r - 1 имеет простой делитель q 4л/г log п и q\or{n).

Доказательство. Оценим число N простых чисел в интервале [а1 (logn)6,a2(log n)6], удовлетворяющих условию

Р(r - 1) > (a2(logn)6)2/3 >r2/3

(будем называть такие числа специальными). Согласно теореме