Повсеместно используемым является простой алгоритм, разработанный Майклом Рабином (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 = z2 mod/; и вернитесь на этап (4). Если z =р - 1, то р проходит проверку и может быть простым числом.
(6) Если; — Ьиг Фр - 1,то/;не является простым числом.
В этом тесте вероятность прохождения проверки составным числом убывает быстрее, чем в предыдущих. Гарантируется, что три четверти возможных значений а окажутся свидетелями. Это означает, что составное число проскользнет через t проверок с вероятностью не большей (1/4)(, где t - это число итераций. На самом деле и эти оценки слишком пессимистичны. Для большинства случайных чисел около 99.9 процентов возмо ж-
ных значений а являются свидетелями [96].
Существуют более точные оценки [417]. Для и-битового кандидата в простые числа (где п больше 100), ве-
роятность ошибки в одном тесте меньше, чем Ап2{/2) . И для 256-битового п вероятность ошибки в шести тестах меньше, чем 1/251. Дополнительную теорию можно найти в [418].