Введение в криптографию
[an error occurred while processing this directive]

Как строить большие простые числа


Мы не будем описывать здесь историю этой задачи, рекомендуем обратиться к книге [] и обзорам [,]. Конечно же, большие простые числа можно строить сравнительно быстро. При этом можно обеспечить их случайное распределение в заданном диапазоне величин. В противном случае теряла бы всякий практический смысл система шифрования RSA. Наиболее эффективным средством построения простых чисел является несколько модифицированная малая теорема Ферма.

Теорема 4.   Пусть , - нечетные натуральные числа,

, причем для каждого простого делителя числа существует целое число такое, что

(10)

Тогда каждый простой делитель числа удовлетворяет сравнению

Доказательство.

Пусть - простой делитель числа , а - некоторый делитель . Из условий () следует, что в поле вычетов справедливы соотношения

(11)

Обозначим буквой порядок элемента в мультипликативной группе поля . Первые два из соотношений () означают, что входит в разложение на простые множители числа в степени такой же, как и в разложение , а последнее - что делится на . Таким образом, каждый простой делитель числа входит в разложение в степени не меньшей, чем в , так что делится на . Кроме того, четно. Теорема 2 доказана.

Следствие .   Если выполнены условия теоремы 2 и , то  - простое число.

Действительно, пусть равняется произведению не менее двух простых чисел. Каждое из них, согласно утверждению теоремы 2, не меньше, чем . Но тогда . Противоречие и доказывает следствие.

Покажем теперь, как с помощью последнего утверждения, имея большое простое число , можно построить существенно большее простое число . Выберем для этого случайным образом четное число на промежутке

и положим . Затем проверим число на отсутствие малых простых делителей, разделив его на малые простые числа; испытаем некоторое количество раз с помощью алгоритма 5. Если при этом выяснится, что  - составное число, следует выбрать новое значение и опять повторить вычисления. Так следует делать до тех пор, пока не будет найдено число , выдержавшее испытания алгоритмом 5 достаточно много раз. В этом случае появляется надежда на то, что  - простое число, и следует попытаться доказать простоту с помощью тестов теоремы 2.




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]