Solovay-Strassen

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

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

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

(3) Вычислите j = a(p-1)/2 mod p.

(4) Вычислите символ Якоби J(a,p).

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

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

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

Lehmann

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

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

(2) Вычислите a^(p-1)/2 mod p.

(3) Если a^(p-1)/2 ¹ 1 или -1 (mod p), то p не является простым.

(4) Если a^(p-1)/2 º 1 или -1 (mod p), то вероятность того, что число p не является простым, не больше 50 процентов.

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

Rabin-Miller

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

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

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

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

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

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

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

(6) Если j = b и z ¹ p - 1, то p не является простым числом.

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

Существуют более точные оценки [417]. Для n-битового кандидата в простые числа (где n больше 100), вероятность ошибки в одном тесте меньше, чем . И для 256-битового n вероятность ошибки в шести тестах меньше, чем 1/2⁵¹. Дополнительную теорию можно найти в [418].