Как строить большие простые числа
Мы не будем описывать здесь историю этой задачи, рекомендуем обратиться к книге [] и обзорам [,]. Конечно же, большие простые числа можно строить сравнительно быстро. При этом можно обеспечить их случайное распределение в заданном диапазоне величин. В противном случае теряла бы всякий практический смысл система шифрования RSA. Наиболее эффективным средством построения простых чисел является несколько модифицированная малая теорема Ферма.
Теорема 4. Пусть , - нечетные натуральные числа,
, причем для каждого простого делителя числа существует целое число такое, что
|
(10) |
Тогда каждый простой делитель числа удовлетворяет сравнению
Доказательство.
Пусть - простой делитель числа , а - некоторый делитель . Из условий () следует, что в поле вычетов справедливы соотношения
|
(11) |
Обозначим буквой порядок элемента в мультипликативной группе поля . Первые два из соотношений () означают, что входит в разложение на простые множители числа в степени такой же, как и в разложение , а последнее - что делится на . Таким образом, каждый простой делитель числа входит в разложение в степени не меньшей, чем в , так что делится на . Кроме того, четно. Теорема 2 доказана.
Следствие . Если выполнены условия теоремы 2 и , то - простое число.
Действительно, пусть равняется произведению не менее двух простых чисел. Каждое из них, согласно утверждению теоремы 2, не меньше, чем . Но тогда . Противоречие и доказывает следствие.
Покажем теперь, как с помощью последнего утверждения, имея большое простое число , можно построить существенно большее простое число . Выберем для этого случайным образом четное число на промежутке
и положим . Затем проверим число на отсутствие малых простых делителей, разделив его на малые простые числа; испытаем некоторое количество раз с помощью алгоритма 5. Если при этом выяснится, что - составное число, следует выбрать новое значение и опять повторить вычисления. Так следует делать до тех пор, пока не будет найдено число , выдержавшее испытания алгоритмом 5 достаточно много раз. В этом случае появляется надежда на то, что - простое число, и следует попытаться доказать простоту с помощью тестов теоремы 2.
Для этого можно случайным образом выбирать число ,
| (12) |
Предположим, что построенное число действительно является простым. Зададимся вопросом, сколь долго придется перебирать числа , пока не будет найдено такое, для которого будут выполнены условия (). Заметим, что для простого числа первое условие (), согласно малой теореме Ферма, будет выполняться всегда. Те же числа , для которых нарушается второе условие (), удовлетворяют сравнению . Как известно, уравнение в поле вычетов имеет не более решений. Одно из них . Поэтому на промежутке чисел, для которых не выполняются условия (). Это означает, что, выбирая случайным образом числа на промежутке можно с вероятностью большей, чем , найти число , для которого будут выполнены условия теоремы 2, и тем доказать, что действительно является простым числом.
Заметим, что построенное таким способом простое число будет удовлетворять неравенству S^2 $" width="58" height="33" >, т.е. будет записываться вдвое большим количеством цифр, чем исходное простое число . Заменив теперь число на найденное простое число и повторив с этим новым все указанные выше действия, можно построить еще большее простое число. Начав с какого-нибудь простого числа, скажем, записанного 10 десятичными цифрами (простоту его можно проверить, например, делением на маленькие табличные простые числа), и повторив указанную процедуру достаточное число раз, можно построить простые числа нужной величины.
Обсудим теперь некоторые теоретические вопросы, возникающие в связи с нахождением простых чисел вида , где числа и удовлетворяют неравенствам . Прежде всего, согласно теореме Дирихле, доказанной еще в 1839 г., прогрессия , содержит бесконечное количество простых чисел. Нас интересуют простые числа, лежащие недалеко от начала прогрессии. Оценка наименьшего простого числа в арифметической прогрессии была получена в 1944 г. Ю.В.Линником. Соответствующая теорема утверждает, что наименьшее простое число в арифметической прогрессии не превосходит , где - некоторая достаточно большая абсолютная постоянная. В предположении справедливости расширенной гипотезы Римана можно доказать, [, с. 272], что наименьшее такое простое число не превосходит при любом положительном .
Таким образом, в настоящее время никаких теоретических гарантий для существования простого числа , не существует. Тем не менее, опыт вычислений на ЭВМ показывает, что простые числа в арифметической прогрессии встречаются достаточно близко к ее началу. Упомянем в этой связи гипотезу о существовании бесконечного количества простых чисел с условием, что число также простое, т.е. простым является уже первый член прогрессии.
Очень важен в связи с описываемым методом построения простых чисел также вопрос о расстоянии между соседними простыми числами в арифметической прогрессии. Ведь убедившись, что при некотором число составное, можно следующее значение взять равным и действовать так далее, пока не будет найдено простое число . И если расстояние между соседними простыми числами в прогрессии велико, нет надежды быстро построить нужное число . Перебор чисел до того момента, как мы наткнемся на простое число окажется слишком долгим. В более простом вопросе о расстоянии между соседними простыми числами и в натуральном ряде доказано лишь, что , что, конечно, не очень хорошо для наших целей. Вместе с тем существует так называемая гипотеза Крамера (1936 г.), что
, дающая вполне приемлемую оценку. Примерно такой же результат следует и из расширенной гипотезы Римана. Вычисления на ЭВМ показывают, что простые числа в арифметических прогрессиях расположены достаточно плотно.
В качестве итога обсуждения в этом разделе подчеркнем следующее: если принять на веру, что наименьшее простое число, а также расстояние между соседними простыми числами в прогрессии при
оцениваются величиной , то описанная схема построения больших простых чисел имеет полиномиальную оценку сложности. Кроме того, несмотря на отсутствие теоретических оценок времени работы алгоритмов, отыскивающих простые числа в арифметических прогрессиях со сравнительно большой разностью, на практике эти алгоритмы работают вполне удовлетворительно. На обычном персональном компьютере без особых затрат времени строятся таким способом простые числа порядка .
Конечно, способ конструирования простых чисел для использования в
должен быть массовым, а сами простые числа должны быть в каком-то смысле хорошо распределенными. Это вносит ряд дополнительных осложнений в работу алгоритмов. Впрочем, описанная схема допускает массу вариаций. Все эти вопросы рассматриваются в статье [].
Наконец, отметим, что существуют методы построения больших простых чисел, использующие не только простые делители , но и делители чисел , , . В основе их лежит использование последовательностей целых чисел, удовлетворяющих линейным рекуррентным уравнениям различных порядков. Отметим, что последовательность , члены которой присутствуют в формулировке малой теоремы Ферма, составляет решение рекуррентного уравнения первого порядка , .
Next: 4.6. Как проверить большое
Up: 4. Алгоритмические проблемы теории
Previous: 4.4. Как отличить составное
Contents:
