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

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


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

(12)

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

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

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

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




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


[an error occurred while processing this directive]