Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Книги
 Обсудить в форуме  Добавить новое сообщение
Next: 4.6. Как проверить большое Up: 4. Алгоритмические проблемы теории Previous: 4.4. Как отличить составное Contents: Содержание

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

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

Теорема 4.   Пусть $ N$, $ S$ - нечетные натуральные числа, $ N-1\double=S\cdot R $, причем для каждого простого делителя $ q$ числа $ S$ существует целое число $ a$ такое, что
\begin{displaymath} a^{N-1}\equiv1\pmod N,\quad (a^\frac{N-1}{q}-1, N)=1. \end{displaymath} (10)

Тогда каждый простой делитель $ p$ числа $ N$ удовлетворяет сравнению

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

Доказательство. Пусть $ p$ - простой делитель числа $ N$, а $ q$ - некоторый делитель $ S$. Из условий (10) следует, что в поле вычетов $ \FF_p$ справедливы соотношения
\begin{displaymath} a^{N-1}=1, a^{\frac{N-1}{q}}\ne1, a^{p-1}=1. \end{displaymath} (11)

Обозначим буквой $ r$ порядок элемента $ a$ в мультипликативной группе поля $ \FF_p$. Первые два из соотношений (11) означают, что $ q$ входит в разложение на простые множители числа $ r$ в степени такой же, как и в разложение $ N-1$, а последнее - что $ p-1$ делится на $ r$. Таким образом, каждый простой делитель числа $ S$ входит в разложение $ p-1$ в степени не меньшей, чем в $ S$, так что $ p-1$ делится на $ S$. Кроме того, $ p-1$ четно. Теорема 2 доказана. $ \qedsymbol$

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

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

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

Для этого можно случайным образом выбирать число $ a$, $ 1<a<N$, и проверять для него выполнимость соотношений
\begin{displaymath} a^{N-1}\equiv1\pmod N, \quad (a^R-1,N)=1. \end{displaymath} (12)

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

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

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

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

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

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

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

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

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

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100