Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 13.7.6 Замечания Вверх: 13.7 Анализ алгоритма построения больших простых чисел, изложенного в Стандарте (ГОСТ Р 34.10-94) "Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма" Назад: 13.7.4 Распознает ли Алгоритм все простые числа?   Содержание   Предметный указатель

13.7.5 Отсеивание составных чисел

Можно добиться существенного сокращения времени работы Алгоритма, если предусмотреть в нем специальные приемы обработки составных чисел.

Составные числа вида $ M=2kq+1$ отсеиваются в Алгоритме с помощью теста теоремы 8. Но для большинства из них непростоту можно доказать значительно быстрее. Так каждое третье число в прогрессии делится на 3, каждое пятое делится на 5 и т. д. Пользуясь регулярностью расположения этих чисел, их можно вообще не рассматривать, перескакивая через них при выборе нового значения u в шаге 8 Алгоритма. Это просеивание можно проделать следующим способом.

Определив в пункте 4 Алгоритма очередное четное число $ N$, составим таблицу всех чисел $ d$ из промежутка $ 0\leqslant d\leqslant 15$ с условием, что $ (N+2d)p+1$ и 15 взаимно просты. Это очень просто сделать, заставив $ d$ пробегать все числа $ 0,1,\ldots,15$ и вычисляя наибольший общий делитель 15 и $ (N+2d)p+1$. Вычисления можно еще упростить, если предварительно вычислить остатки от деления на 15 чисел $ N$ и $ p$. Эта таблица чисел $ d$ будет состоять из 8 чисел $ d_1<d_2<\ldots<d_8$. Положим также

$\displaystyle \Delta_i=\begin{cases} 15+d_1-d_8,&\text{если }i=0,\\ d_{i+1}-d_i,&\text{если }1\leqslant i\leqslant 7. \end{cases}$

Вместо одной переменной $ u$ в Алгоритме нужно рассматривать две переменные $ u$ и $ v$, положив в шаге 5 $ u\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-4mu}=d$, $ v\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-4mu}=0$, а затем вычисляя в шаге 8

$\displaystyle v\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-... ...\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-4mu}=u+\Delta_v. $

Легко видеть, что все числа прогрессии $ (N+2u)q+1$, $ u\geqslant 0$, делящиеся на 3 или 5, будут при этом пропущены.

Можно расширить количество маленьких делителей, добавив к множеству $ \{3,5\}$ число $ 7,11$ и т. д. При этом доля остающихся в результате просеивания чисел будет равна соответственно

$\displaystyle \frac{2\cdot4\cdot6}{3\cdot5\cdot7}=0,457\ldots,\qquad \frac{2\cdot4\cdot6\cdot10}{3\cdot5\cdot7\cdot11}=0,415\ldots$   и т. д.

Отметим, что длина таблицы остатков будет при этом равна $ 48,480,\ldots$, т. е. будет довольно быстро увеличиваться.

Иной вариант организации просеивания, не использующий много памяти, но требующий несколько большего объема вычислений, можно реализовать так. Будем использовать вместо одной переменной $ v$ две переменные $ v_1$ и $ v_2$, которые будут равны остаткам от деления числа $ (N+u)q+1$ на 3 и 5 соответственно. Для этого шаг 5 представим как три следующих шага:   5.1. Положить

\begin{displaymath} \begin{gathered}u\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1... ...ebox{1.1pt}{\rm .}\mspace{-4mu}=(2p_{m+1})\bmod 5.\end{aligned}\end{displaymath}

  5.2. Если $ v_1\ne0$ и $ v_2\ne0$, перейти в пункт 6.

  5.3. Положить

$\displaystyle u\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-... ...{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-4mu}=(v_2+d_2)\bmod 3 $

и перейти в шаг 5.2.

Кроме того, приведенный выше пункт 8.5 Алгоритма нужно изменить следующим образом:   8.5. Перейти в пункт 5.3.

Как и выше, можно увеличить множество простых делителей $ \{3,5\}$, добавив к ним числа $ 7,11$ и т. д.

Описанные выше приемы просеивания, исключают из рассмотрения числа $ M=(N+u)p_{m+1}+1$, имеющие маленькие простые делители. В качестве еще одного средства отсеивания составных чисел $ M$ можно использовать следующие изменения в пункте 7:     7. Если $ p_m>2^{t_m}$, то перейти к шагу 4. В противном случае проверить делимость числа $ p_m$ на все простые числа, не превосходящие некоторой границы $ B$. В случае делимости вычислить новое значение $ u$ (перейти в пункт 5.3).

Для реализации этого пункта нужно предварительно, скажем, в пункте 1 Алгоритма запасти таблицу всех простых чисел, не превосходящих $ B$.

После указанных в этом параграфе изменений к тестам пункта 8 будут приходить только числа $ M=(N+u)p_{m+1}+1$, все простые делители которых превосходят границу $ B$.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 13.7.6 Замечания Вверх: 13.7 Анализ алгоритма построения больших простых чисел, изложенного в Стандарте (ГОСТ Р 34.10-94) "Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма" Назад: 13.7.4 Распознает ли Алгоритм все простые числа?   Содержание   Предметный указатель

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