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

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

Пусть 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.