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


13.7.2 Алгоритм

В основу используемого в Стандарте алгоритма построения больших простых чисел $ p$ положена следующая теорема (отметим, что в Стандарте отсутствуют ссылки на какую-нибудь научную литературу, что создает определенные трудности при анализе).

Теорема 8.  Пусть $ M=2kq+1$, $ k\in\mathbb{Z}$, где $ q$ -- нечетное простое число, $ a$ -- натуральное число, взаимно простое с $ M$, и

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

Тогда, если $ k\leqslant 2q+1$ то $ M$ -- простое число.

В Алгоритме эта теорема используется при $ a=2$.

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

$\displaystyle p_s<p_{s-1}<\ldots<p_0 $

длины $ t_s<t_{s-1}<\ldots<t_0$ соответственно, причем $ t_{i+1}=[t_i/2]$, $ i=0,\ldots,s-1$, $ t_s<17$. При этом построение начинается с $ p_s$ и для $ i=s-1,s-2,\ldots,0$ число $ p_i$ строится по $ p_{i+1}$ в виде

$\displaystyle p_i=2kp_{i+1}+1 $

и число $ k$ всякий раз подбирается так, чтобы при $ a=2$ были выполнены условия теоремы 8. Простые числа $ p=p_0$ и $ q=p_1$ имеют все необходимые свойства. Дадим теперь формальное описание Алгоритма. При этом мы опускаем построение последовательности случайных чисел $ \xi$, равномерно распределенной на интервале $ (0,1)$. Для наших целей это построение не принципиально.


Алгоритм построения простых чисел $ p$ и $ q$, $ q\mid(p-1)$, имеющих длину соответственно $ t$ и $ [t/2]$ битов:     1. Вычислить последовательность чисел $ (t_0,t_1,\ldots,t_s)$ по правилу:

$ t_0\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-4mu}=t$;

если $ t_i\geqslant 17$, то $ t_{i+1}=[t_i/2]$;

если $ t_i<17$, то $ s=i$.

    2. Найти наименьшее простое число $ p_s$ длины $ t_s$ битов.

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

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

$\displaystyle N=\left\lceil2^{t_m-1}/p_{m+1}\right\rceil+ \left[\left(2^{t_m-1}\cdot\xi\right)/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. $ u\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-4mu}=0$.

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

    7. Если $ p_m>2^{t_m}$, то перейти к шагу 4.

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

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

Если хотя бы одно из условий не выполнено, то положить $ u\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-4mu}=u+2$, и перейти к шагу 6. Если выполнены оба условия, то положить $ 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$ -- искомые простые числа.

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

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