Генерация простых чисел

Для алгоритмов с открытыми ключами нужны простые числа. Их нужно множество для любой достаточно большой сети, хватит ли их? 

Да, существует приблизительно 10¹⁵¹ простых чисел длиной до 512 бит включительно. Для чисел, близких m, вероятность того, что случайно выбранное число окажется простым, равна 1/ ln m. Поэтому полное число простых чисел, меньших m, равно m /(ln m). При выборе из 10¹⁵¹ простых чисел вероятность совпадения выбора практически равна нулю.

  Но если так трудоемко разложение на множители, как может быть простой генерация простых чисел? Дело в том, что ответить "да" или "нет" на вопрос "является ли число простым?" гораздо проще, чем ответить на более сложный вопрос "каковы множители m?"

Генерация случайных чисел с последующей попыткой разложения их на множители - это неправильный способ поиска простых чисел. Сущест­вуют различные вероятностные проверки на простоту чисел, определяющие, является ли число простым, с заданной степенью достоверности. При условии, что эта «степень достоверности» достаточно велика, такие способы проверки достаточно хороши.

Предлагаются [6] следующие тесты проверки чисел на простоту:

Тест Леманна (Lehmann)

Вот последовательность действий при проверке простоты числа р;

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

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

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

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

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

Алгоритм Рабина-Миллера (Rabin-Miller)

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

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

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

2) Установите j = 0 и z = a · m mod p.

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

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

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

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

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

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