Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 14. Односторонние функции и псевдослучайные генераторы Вверх: 13. Методы построения больших простых чисел Назад: 13.7.6 Замечания   Содержание   Предметный указатель


13.8 Алгоритм построения простых чисел

Описываемый ниже алгоритм построения больших простых чисел является модификацией Алгоритма из раздела 13.7, учитывающей высказанные в этом разделе замечания. Для его работы требуется таблица всех нечетных простых чисел, меньших $ 2^{17}$. Такая таблица легко может быть составлена, например, проверкой делимости на нечетные числа, не превосходящие 361 (ведь $ 363^2>2^{17}$). По заданным целым числам $ X$, $ Y$ и $ Z$, $ T$, $ 8Z^2>Y$, предлагаемый алгоритм строит простые числа $ p$ и $ q$ с условиями

$\displaystyle X<p<Y,\qquad Z<q<T,\qquad q\mid (p-1).$ (11)

Например, для $ X=2^{t-1}$, $ Y=2^t$, $ Z=2^{[t/2]-1}$, $ T=2^{[t/2]}$ получаются простые числа $ p$ и $ q$, имеющие битовую длину соответственно $ t$ и $ [t/2]$.


Алгоритм     1. Вычислить две последовательности чисел

\begin{displaymath} \begin{aligned} X_0&=X,\quad X_1=Z,\\ X_{r+1}&=\left\lceil\... ...egin{gathered}\null\\ 1\leqslant r\leqslant s-1, \end{gathered}\end{displaymath}

где число $ s$ выбрано так, что $ Y_s<2^{34}$.

    2. Найти простое число $ p_s$, удовлетворяющее неравенствам $ X_s<p_s<Y_s$. Это можно сделать, перебирая случайным образом нечетные числа на указанном промежутке и проверяя их делимость на все простые, меньшие $ 2^{17}$.

    3. $ m\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-4mu}=s-1$

    4. Вычислить случайное число $ \xi$ на интервале $ (0;1)$ и положить

$\displaystyle N=\left\lceil X_m/p_{m+1}\right\rceil+ \left[(X_m\cdot\xi)/p_{m+1}\right]. $

(Здесь [x] и $ \lceil x\rceil$ обозначают целую часть числа $ x$ и наименьшее целое, не меньшее, чем $ x$.) Если $ N$ нечетно, положить $ N\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-4mu}=N+1$.

    5. (В этом пункте алгоритма отсеиваются числа $ (N+u)p_{m+1}+1$, делящиеся на 3 или на 5.)   5.1. Положить $ u\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-4mu}=0$ и для $ r_1=3$, $ r_2=5$, $ r_3=7$, $ r_4=11$, $ r_5=13$, $ r_6=17$ вычислить

$\displaystyle v_k\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace... ....1pt}{\rm .}\mspace{-4mu}= (2p_{m+1})\bmod r_k,\qquad 1\leqslant k\leqslant 6. $

  5.2. Если для всех $ k$, $ 1\leqslant k\leqslant 6$, выполняется $ v_k\ne0$, перейти в пункт 6.

  5.3. Положить

$\displaystyle u\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-... ...x{1.1pt}{\rm .}\mspace{-4mu}=(v_k+d_k)\bmod r_k,\qquad 1\leqslant k\leqslant 6 $

и перейти в пункт 5.2.

    6. Вычислить $ p_m=(N+u)p_{m+1}+1$.

    7. Если $ p_m\geqslant Y_m$, то перейти к пункту 4. В противном случае проверить делимость числа $ p_m$ на все простые числа, не превосходящие $ 2^{17}$. В случае делимости на какое-нибудь из указанных чисел перейти в пункт 5.3.

    8. Ниже в этом пункте реализованы тесты проверки на простоту, описанные в теоремах 9 и 10 из раздела 13.7).   8.1. Положить $ a\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-4mu}=1$. Вычислить целое $ s$ и нечетное число $ d$ такие, что $ (N+u)p_{m+1}=2^s\cdot d$.

  8.2. Положить $ a\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-4mu}=a+1$.

  8.3. Проверить условие

$\displaystyle a^d\not\equiv 1\mkern5mu({\rm mod}\,\,p_m). $

Если это условие нарушается, перейти в пункт 8.6.

  8.4. При каждом $ i$, $ 0\leqslant i\leqslant s-1$, проверить условие

$\displaystyle a^{2^id}\not\equiv 1\mkern5mu({\rm mod}\,\,M). $

Если оно нарушается хотя бы при одном $ i$, перейти в пункт 8.6.

  8.5. Перейти в пункт 5.3.

  8.6. Проверить условие

$\displaystyle a^{(N+u)}\not\equiv 1\mkern5mu({\rm mod}\,\,p_m).$

Если это условие не выполняется, перейти в пункт 8.2.

  8.7. Проверить условие

$\displaystyle p_m\ne(2p_{m+1}+1)^2. $

Если это условие не выполняется, перейти в пункт 8.2.

  8.8. Положить $ m\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-4mu}=m-1$.

    9. Если $ m\geqslant 0$, то перейти к пункту 4. Если же $ m<0$, то $ p=p_0$ и $ q=p_1$ -- искомые простые числа.

Отметим, что простота числа $ q$ обеспечивается теоремой 9 из раздела 13.7. По этой же теореме в силу неравенств

$\displaystyle k=\frac{p-1}{2q}\leqslant\frac{Y}{2Z}\leqslant 4Z<4q+2 $

простым будет и число $ p$.

Вышеописанный алгоритм был запрограммирован на языке UBasic, в котором реализованы арифметические операции с целыми числами величиной до $ 2^{8600}$. Соответствующая программа была применена для построения двух таблиц простых чисел $ p$ и соответствующих простых делителей $ q$, $ q\mid(p-1)$. В первой содержатся 20 простых чисел $ p$, длина записи которых равна 512 битов, а во второй -- 15 чисел $ p$ с длиной записи 1024 битов. На составление первой таблицы персональный компьютер с процессором 80386/7 потратил 9 мин. 20 сек., а на составление второй -- 30 мин. машинного времени.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 14. Односторонние функции и псевдослучайные генераторы Вверх: 13. Методы построения больших простых чисел Назад: 13.7.6 Замечания   Содержание   Предметный указатель

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