ЗАРОЖДЕНИЕ КРИПТОГРАФИИ

       

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


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

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

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

(10)

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

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

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



(11)

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

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

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

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

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


Для этого можно случайным образом выбирать число ,

(12)
Если при выбранном эти соотношения выполняются, то, согласно следствию из теоремы 2, можно утверждать, что число простое. Если же эти условия нарушаются, нужно выбрать другое значение и повторять эти операции до тех пор, пока такое число не будет обнаружено.

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

Заметим, что построенное таким способом простое число будет удовлетворять неравенству S^2 $" width="58" height="33" >, т.е. будет записываться вдвое большим количеством цифр, чем исходное простое число . Заменив теперь число на найденное простое число и повторив с этим новым все указанные выше действия, можно построить еще большее простое число. Начав с какого-нибудь простого числа, скажем, записанного 10 десятичными цифрами (простоту его можно проверить, например, делением на маленькие табличные простые числа), и повторив указанную процедуру достаточное число раз, можно построить простые числа нужной величины.

Обсудим теперь некоторые теоретические вопросы, возникающие в связи с нахождением простых чисел вида , где числа и удовлетворяют неравенствам . Прежде всего, согласно теореме Дирихле, доказанной еще в 1839 г., прогрессия , содержит бесконечное количество простых чисел. Нас интересуют простые числа, лежащие недалеко от начала прогрессии. Оценка наименьшего простого числа в арифметической прогрессии была получена в 1944 г. Ю.В.Линником. Соответствующая теорема утверждает, что наименьшее простое число в арифметической прогрессии не превосходит , где  - некоторая достаточно большая абсолютная постоянная. В предположении справедливости расширенной гипотезы Римана можно доказать, [, с. 272], что наименьшее такое простое число не превосходит при любом положительном .




Таким образом, в настоящее время никаких теоретических гарантий для существования простого числа , не существует. Тем не менее, опыт вычислений на ЭВМ показывает, что простые числа в арифметической прогрессии встречаются достаточно близко к ее началу. Упомянем в этой связи гипотезу о существовании бесконечного количества простых чисел с условием, что число также простое, т.е. простым является уже первый член прогрессии.

Очень важен в связи с описываемым методом построения простых чисел также вопрос о расстоянии между соседними простыми числами в арифметической прогрессии. Ведь убедившись, что при некотором  число составное, можно следующее значение  взять равным и действовать так далее, пока не будет найдено простое число . И если расстояние между соседними простыми числами в прогрессии велико, нет надежды быстро построить нужное число . Перебор чисел  до того момента, как мы наткнемся на простое число  окажется слишком долгим. В более простом вопросе о расстоянии между соседними простыми числами и в натуральном ряде доказано лишь, что , что, конечно, не очень хорошо для наших целей. Вместе с тем существует так называемая гипотеза Крамера (1936 г.), что

, дающая вполне приемлемую оценку. Примерно такой же результат следует и из расширенной гипотезы Римана. Вычисления на ЭВМ показывают, что простые числа в арифметических прогрессиях расположены достаточно плотно.

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

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




Конечно, способ конструирования простых чисел для использования в

должен быть массовым, а сами простые числа должны быть в каком-то смысле хорошо распределенными. Это вносит ряд дополнительных осложнений в работу алгоритмов. Впрочем, описанная схема допускает массу вариаций. Все эти вопросы рассматриваются в статье [].

Наконец, отметим, что существуют методы построения больших простых чисел, использующие не только простые делители , но и делители чисел , , . В основе их лежит использование последовательностей целых чисел, удовлетворяющих линейным рекуррентным уравнениям различных порядков. Отметим, что последовательность , члены которой присутствуют в формулировке малой теоремы Ферма, составляет решение рекуррентного уравнения первого порядка , .

Next: 4.6. Как проверить большое

Up: 4. Алгоритмические проблемы теории

Previous: 4.4. Как отличить составное

Contents:



Содержание раздела