Нестеренко Ю.В.

Наиболее эффективным средством построения простых чисел являетсянесколько модифицированная малая теорема Ферма.

Пусть N, S --- нечётные натуральные числа, N-1 = S*R, причем длякаждого простого делителя q числа S существует целое число a такое, что

Тогда каждый простой делитель p числа N удовлетворяет сравнению p = 1(mod 2S)

Если выполнены условия теоремы Ферма и R <= 4S+2, то N --- простоечисло.

Покажем теперь, как с помощью последнего утверждения, имея большоепростое число S, можно построить существенно большее простое число N.Выберем для этого случайным образом чётное число R на промежуткеR <= 4S+2 и положим N=SR+1. Затем проверим число N на отсутствиемалых простых делителей, разделив его на малые простые числа;испытаем N некоторое количество раз с помощьюалгоритма Рабина. Если при этом выяснится, что N --- составное число, следует выбратьновое значение R и опять повторить вычисления. Так следует делать до тех пор,пока не будет найдено число N,выдержавшее испытания алгоритмом Рабина достаточномного раз. В этом случае появляется надежда на то, что N ---простое число, иследует попытаться доказать простоту с помощью тестов теоремы 2.

Для этого можно случайным образом выбирать число a, 1 < a < N, ипроверять для него выполнимость соотношений a^N-1=1(mod N), НОД(a^R-1, N)=1.

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

Предположим, что построенное число N действительно является простым.Зададимся вопросом, сколь долго придётся перебирать числа a, пока не будетнайдено такое, для которого будут выполнены условия (12). Заметим, что дляпростого числа N первое условие (12), согласно малой теореме Ферма, будетвыполняться всегда. Те же числа a, для которых нарушается второе условие (12),удовлетворяют сравнению a^R=1(mod N). Как известно, уравнение x^R=1 в полевычетов F_n имеет не более R решений. Одно из них x=1.Поэтому на промежутке 1 < a < N имеется не более R-1 чисел, для которых не выполняются условия (12).

Это означает, что, выбирая случайным образом числа a на промежутке 1 < a < N,припростом N можно с вероятностью большей, чем 1-O(S^-1), найти число a, длякоторого будут выполнены условия теоремы Ферма, и тем доказать, что Nдействительно является простым числом.

Заметим, что построенное таким способом простое число N будетудовлетворять неравенству N>S², т.е. будет записываться вдвое большимколичеством цифр, чем исходное простое число S. Заменив теперь число S нанайденное простое число N и повторив с этим новым S все указанные вышедействия, можно построить ещё большее простое число. Начав с какого-нибудьпростого числа, скажем, записанного 10 десятичными цифрами (простоту егоможно проверить, например, делением на маленькие табличные простые числа), иповторив указанную процедуру достаточное число раз, можно построить простыечисла нужной величины.

Обсудим теперь некоторые теоретические вопросы, возникающие в связи снахождением числа R, удовлетворяющего неравенствам S <= R <= 4S+2, и такого,что N=SR+1 -- простое число. Прежде всего, согласно теореме Дирихле,доказанной ещё в 1839г., прогрессия 2Sn+1, n=1,2,3,... содержит бесконечноеколичество простых чисел. Нас интересуют простые числа, лежащие недалеко отначала прогрессии. Оценка наименьшего простого числа в арифметическойпрогрессии была получена в 1944г. Ю.В.Линником. Соответствующая теоремаутверждает, что наименьшее простое число в арифметической прогрессии 2Sn+1не превосходит S^C, где C -- некоторая достаточно большая абсолютнаяпостоянная. В предположении справедливости расширенной гипотезы Риманаможно доказать, что наименьшее такое простое число непревосходит c(e)*S^2+e при любом положительном e.

Таким образом, в настоящее время никаких теоретических гарантий длясуществования простого числа N=SR+1, S < R < 4S+2 не существует. Тем неменее опыт вычислений на ЭВМ показывает, что простые числа варифметической прогрессии встречаются достаточно близко к её началу.Упомянем в этой связи гипотезу о существовании бесконечного количествапростых чисел q с условием, что число 2q+1 также простое, т.е.простым является уже первый член прогрессии.

Очень важен в связи с описываемым методом построения простых чиселтакже вопрос о расстоянии между соседними простыми числами варифметической прогрессии. Ведь убедившись, что при некотором R числоN=SR+1 составное, можно следующее значение R взять равным R+2 идействовать так далее, пока не будет найдено простое число N.

И если расстояниемежду соседними простыми числами в прогрессии велико, нет надежды быстропостроить нужное число N. Перебор чисел Rдо того момента, как мы наткнемсяна простое число N окажется слишком долгим. В более простом вопросе орасстоянии между соседними простыми числами p_n и p_n+1 в натуральном рядедоказано лишь, что p_n+1-p_n=O(p_n^38/61+e), что, конечно, не очень хорошо для нашихцелей. Вместе с тем существует так называемая гипотезаКрамера (1936г.), что p_n+1-p_n=O(ln²p_n), дающая вполне приемлемую оценку. Примерно такой жерезультат следует и из расширенной гипотезы Римана. Вычисления на ЭВМпоказывают, что простые числа в арифметических прогрессиях расположеныдостаточно плотно.

В качестве итога обсуждения в этом пункте подчеркнём следующее: еслипринять на веру, что наименьшее простое число, а также расстояние междусоседними простыми числами в прогрессии 2Sn+1 при S <= n <= 4S+2 оцениваются величиной O(ln²S), то описанная схема построения большихпростых чисел имеет полиномиальную оценку сложности. Кроме того, несмотряна отсутствие теоретических оценок времени работы алгоритмов, отыскивающихпростые числа в арифметических прогрессиях со сравнительно большойразностью, на практике эти алгоритмы работают вполне удовлетворительно. Наобычном персональном компьютере без особых затрат времени строятся такимспособом простые числа порядка 10³⁰⁰.

Конечно, способ конструирования простых чисел для использования в схеме RSAдолжен быть массовым, а сами простые числа должны быть в каком-то смыслехорошо распределёнными. Это вносит ряд дополнительных осложнений в работуалгоритмов. Впрочем, описанная схема допускает массу вариаций.

Наконец, отметим, что существуют методы построения больших простыхчисел, использующие не только простые делители N-1, но и делители чиселN+1, N²+1, N² +- N+1 $. В основе их лежит использование последовательностейцелых чисел, удовлетворяющих линейным рекуррентным уравнениям различныхпорядков. Отметим, что последовательность aⁿ, члены которой присутствуют вформулировке малой теоремы Ферма, составляет решение рекуррентногоуравнения первого порядка u_n+1=au_n, u₀=1.