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

Next: 4.6. Как проверить большое Up: 4. Алгоритмические проблемы теории Previous: 4.4. Как отличить составное Contents: Содержание

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

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

Теорема 4. Пусть , - нечетные натуральные числа, $N-1\double=S\cdot R$ , причем для каждого простого делителя числа существует целое число такое, что

$\begin{displaymath} a^{N-1}\equiv1\pmod N,\quad (a^\frac{N-1}{q}-1, N)=1. \end{displaymath}$ (10)

Тогда каждый простой делитель

числа

удовлетворяет сравнению

$\begin{displaymath} p\equiv1\pmod{2S}. \end{displaymath}$

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

$\begin{displaymath} a^{N-1}=1, a^{\frac{N-1}{q}}\ne1, a^{p-1}=1. \end{displaymath}$ (11)

Обозначим буквой

порядок элемента

в мультипликативной группе поля $\FF_p$ . Первые два из соотношений (11) означают, что

входит в разложение на простые множители числа

в степени такой же, как и в разложение

, а последнее - что

делится на

. Таким образом, каждый простой делитель числа

входит в разложение

в степени не меньшей, чем в

, так что

делится на

. Кроме того,

четно. Теорема 2 доказана. $\qedsymbol$

Следствие . Если выполнены условия теоремы 2 и $R\leq 4S+2$ , то - простое число.

Действительно, пусть равняется произведению не менее двух простых чисел. Каждое из них, согласно утверждению теоремы 2, не меньше, чем . Но тогда $(2S+1)^2\leq N=SR+1\leq 4S^2+2S+1$ . Противоречие и доказывает следствие.

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

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

$\begin{displaymath} a^{N-1}\equiv1\pmod N, \quad (a^R-1,N)=1. \end{displaymath}$ (12)

Если при выбранном

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

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

и повторять эти операции до тех пор, пока такое число не будет обнаружено.

Предположим, что построенное число действительно является простым. Зададимся вопросом, сколь долго придется перебирать числа , пока не будет найдено такое, для которого будут выполнены условия (12). Заметим, что для простого числа первое условие (12), согласно малой теореме Ферма, будет выполняться всегда. Те же числа , для которых нарушается второе условие (12), удовлетворяют сравнению $a^R\equiv1\pmod N$ . Как известно, уравнение в поле вычетов $\FF_N$ имеет не более решений. Одно из них . Поэтому на промежутке имеется не более чисел, для которых не выполняются условия (12). Это означает, что, выбирая случайным образом числа на промежутке , при простом можно с вероятностью большей, чем $1-O(S^{-1})$ , найти число , для которого будут выполнены условия теоремы 2, и тем доказать, что действительно является простым числом.

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

Обсудим теперь некоторые теоретические вопросы, возникающие в связи с нахождением простых чисел вида , где числа и удовлетворяют неравенствам $S\leq R\leq 4S+2$ . Прежде всего, согласно теореме Дирихле, доказанной еще в 1839 г., прогрессия , $n=1,2,3,\dots$ содержит бесконечное количество простых чисел. Нас интересуют простые числа, лежащие недалеко от начала прогрессии. Оценка наименьшего простого числа в арифметической прогрессии была получена в 1944 г. Ю.В.Линником. Соответствующая теорема утверждает, что наименьшее простое число в арифметической прогрессии не превосходит , где - некоторая достаточно большая абсолютная постоянная. В предположении справедливости расширенной гипотезы Римана можно доказать, [11, с. 272], что наименьшее такое простое число не превосходит $c(\varepsilon )\cdot S^{2+\varepsilon }$ при любом положительном $\varepsilon$ .

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

Очень важен в связи с описываемым методом построения простых чисел также вопрос о расстоянии между соседними простыми числами в арифметической прогрессии. Ведь убедившись, что при некотором число составное, можно следующее значение взять равным и действовать так далее, пока не будет найдено простое число . И если расстояние между соседними простыми числами в прогрессии велико, нет надежды быстро построить нужное число . Перебор чисел до того момента, как мы наткнемся на простое число окажется слишком долгим. В более простом вопросе о расстоянии между соседними простыми числами и $p_{n+1}$ в натуральном ряде доказано лишь, что $p_{n+1}-p_n=O\left(p^{\frac{38}{61}+\varepsilon }_n\right)$ , что, конечно, не очень хорошо для наших целей. Вместе с тем существует так называемая гипотеза Крамера (1936 г.), что $p_{n+1}-p_n=O(\ln^2p_n)$ , дающая вполне приемлемую оценку. Примерно такой же результат следует и из расширенной гипотезы Римана. Вычисления на ЭВМ показывают, что простые числа в арифметических прогрессиях расположены достаточно плотно.

В качестве итога обсуждения в этом разделе подчеркнем следующее: если принять на веру, что наименьшее простое число, а также расстояние между соседними простыми числами в прогрессии при $S\leq n \leq 4S+2$ оцениваются величиной $O(\ln^2S)$ , то описанная схема построения больших простых чисел имеет полиномиальную оценку сложности. Кроме того, несмотря на отсутствие теоретических оценок времени работы алгоритмов, отыскивающих простые числа в арифметических прогрессиях со сравнительно большой разностью, на практике эти алгоритмы работают вполне удовлетворительно. На обычном персональном компьютере без особых затрат времени строятся таким способом простые числа порядка $10^{300}$ .

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

Наконец, отметим, что существуют методы построения больших простых чисел, использующие не только простые делители , но и делители чисел , , $N^2\pm N+1$ . В основе их лежит использование последовательностей целых чисел, удовлетворяющих линейным рекуррентным уравнениям различных порядков. Отметим, что последовательность , члены которой присутствуют в формулировке малой теоремы Ферма, составляет решение рекуррентного уравнения первого порядка $u_{n+1}=au_n$ , .