Rabin-Miller

Lehmann

Solovay-Strassen

Роберт Соловэй (Robert Solovay) и Фолькер Штрассен (Volker Strassen) разработали алгоритм вероятностной проверки простоты числа [1490]. Для проверки простоты числа р этот алгоритм использует символ Якоби:

(1) Выберите случайно число а, меньшее/;.

(2) Если НОД(а,/;) (1, тор не проходит проверку и является составным.

(3) Вычислите; = а(р-\)12 mod/;.

(4) Вычислите символ Якоби ](а,р).

(5) Если j Ф J(a,p), то число р наверняка не является простым.

(6) Если; = J(a,p), то вероятность того, что число р не является простым, не больше 50 процентов.

Число а, которое не показывает, что р наверняка не является простым числом, называется свидетелем. Если р - составное число, вероятность случайного числа а быть свидетелем не ниже 50 процентов. Повторите эту проверку г раз с г различными значениями а. Вероятность того, что составное число преодолеет все t проверок, не превышает 1/2⁽.

Другой, более простой тест был независимо разработан Леманном (Lehmann) [903]. Вот последовательность действий при проверке простоты числа р:

(1) Выберите случайно число а, меньшее/;.

(2) Вычислите а^рА'² mod/;.

(3) Если а^рА'² Ф 1 или -1 (mod p), то р не является простым.

(4) Если cfi-V'¹ = 1 или -1 (mod p), то вероятность того, что число р не является простым, не больше 50 про­центов.

И снова, вероятность того, что случайное число а будет свидетелем составной природы числа р, не меньше 50 процентов. Повторите эту проверку t раз. Если результат вычислений равен 1 или -1, но не всегда равен 1, то р является простым числом с вероятностью ошибки I/²'.

Повсеместно используемым является простой алгоритм, разработанный Майклом Рабином (Michael Rabin), частично основанным на идеях Гэри Миллера [1093, 1284]. По сути, это упрощенная версия алгоритма, рек о-мендованного в предложении DSS proposal [1149, 1154].

Выберите для проверки случайное число р. Вычислите Ъ - число делений/; - 1 на 2 (т.е., 2^Ь - это наибольшая степень числа 2, на которое делится р - 1). Затем вычислите тп, такое что/; = 1 + 2^Ъ * т.

(1) Выберите случайное число а, меньшее/;.

(2) Установите; = 0 и z = am mod/;.

(3) Если z = 1 или если г=р- 1,тор проходит проверку и может быть простым числом.

(4) Если; > 0 и z = 1, то р не является простым числом.

(5) Установите; = j + 1. Если; < Ъ и z( p - 1, установите z = z² mod/; и вернитесь на этап (4). Если z =р - 1, то р проходит проверку и может быть простым числом.

(6) Если; — Ьиг Фр - 1,то/;не является простым числом.

В этом тесте вероятность прохождения проверки составным числом убывает быстрее, чем в предыдущих. Гарантируется, что три четверти возможных значений а окажутся свидетелями. Это означает, что составное число проскользнет через t проверок с вероятностью не большей (1/4)⁽, где t - это число итераций. На самом деле и эти оценки слишком пессимистичны. Для большинства случайных чисел около 99.9 процентов возмо ж-

ных значений а являются свидетелями [96].

Существуют более точные оценки [417]. Для и-битового кандидата в простые числа (где п больше 100), ве-

роятность ошибки в одном тесте меньше, чем Ап2^{/2) . И для 256-битового п вероятность ошибки в шести тес­тах меньше, чем 1/2⁵¹. Дополнительную теорию можно найти в [418].