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

13.7.3 Всегда ли результатом работы Алгоритма являются простые числа?

Указанный алгоритм, вообще говоря, может выдавать в качестве $ p$ и $ q$ составные числа.

Выбор $ N$, указанный в пункте 4, и пункт 7 Алгоритма обеспечивают выполнение неравенств

$\displaystyle 2^{t_m-1}<p_m\leqslant 2^{t_m},$ (4)

означающих в силу нечетности $ p_m$, что длина $ p_m$ в точности равняется $ t_m$ битов. Кроме того, если $ t_m$ четно, то $ t_m=2t_{m+1}$ и из (4) следует

$\displaystyle 2k=N+u=\frac{p_m-1}{p_{m+1}}<2^{t_m-t_{m+1}+1}=2^{t_{m+1}+1}<4p_{m+1}, $

т. е. выполнены условия первого пункта теоремы 8 и можно утверждать, что $ p_m$ -- простое число.

Если же $ t_m$ нечетно, то $ t_m=2t_{m+1}+1$ и

$\displaystyle 2k=N+u=\frac{p_m-1}{p_{m+1}}<2^{t_m-t_{m+1}+1}=2^{t_{m+1}+2}<8p_{m+1}. $

При $ p_{m+1}$, близком к своему наименьшему возможному значению $ 2^{t_{m+1}-1}$, возможные для $ N+u$ значения, близкие к $ 2^{t_m}/p_{m+1}$, будут примерно равны $ 2^{t_{m+1}-2}$, т. е. $ 8p_{m+1}$. Это означает, что параметры будут находиться вне пределов справедливости теоремы 8 и, следовательно, гарантировать простоту числа $ p_m$ в таком случае нельзя.

Если исходное значение $ t=2^v$, скажем, 256 или 512, то все числа $ t_m$ четны и все $ p_m$ на основании теоремы 8 просты. Но, если, например, $ t=255$, все числа $ t_m$ нечетны и тогда на каждом шаге Алгоритма нельзя гарантировать простоту $ p_m$ и, следовательно, простоту $ p=p_0$ и $ q=p_1$. Но именно 255 указывается в процедуре В как допустимое значение длины числа $ q$, используемого в алгоритме цифровой подписи.

Указанную неточность в Алгоритме можно исправить несколькими способами.


а) Можно было бы определить последовательность $ t_i$ в шаге 1 Алгоритма равенствами $ t_{i+1}=[(t_i+1)/2]$. Тогда при любом $ m$ выполняется неравенство $ t_m\leqslant 2t_{m+1}$ и из (4) следует

$\displaystyle 2k=N+u=\frac{p_m-1}{p_{m+1}}<2^{t_m-t_{m+1}+1}=2^{t_{m+1}+1}<4p_{m+1}. $

Это в силу теоремы 8 позволяет утверждать, что $ p_m$ -- простое число. При этом битовая длина числа $ q$, получаемого в результате работы Алгоритма, будет равна $ [(t+1)/2]$. При нечетных $ t$ оно будет длиннее на 1 бит.

Если $ t$ равно $ 2^v$, такое изменение Алгоритма не приведет к увеличению числа итераций. Не изменится число итераций и для $ t=255$. А вот для $ t=257$ изменение Алгоритма приведет к увеличению числа итераций на 1.

б) Увеличение диапазона для $ k$ в теореме 8 позволяет при заданном $ q$ строить простые числа, имеющие большую величину. Однако условие $ k\leqslant 2q+1$ в формулировке теоремы ослабить нельзя. Так, возможен случай, когда для составного $ M=(2q+1)^2=2(2q+2)q+1$ выполнены условия (2) и (3). Например, этот случай имеет место     1) при $ q=5$, $ M=11$, $ a=3$;

    2) при $ q=431$, $ M=863$, $ a=13$;

    3) при $ q=641$, $ M=1283$, $ a=45$;

    4) при $ q=3779$, $ M=7559$, $ a=102$;

    5) при $ q=4019$, $ M=8039$, $ a=39$.


В следующей теореме описываются исключительные случаи, которые могут возникать при увеличении интервала возможных значений $ k$ до $ 4q+2$.

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

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

Тогда если $ k\leqslant 4q+2$, то $ M$ -- простое число или $ M=r^2$, где $ r=2q+1$ -- простое число. В последнем случае также выполняется сравнение

$\displaystyle a^{r-1}\equiv 1\mkern5mu({\rm mod}\,\,r^2).$ (5)

Следствие.  Если выполнены условия теоремы 9 и $ M\ne(2q+1)^2$, $ k\leqslant 4q+2$, то $ M$ -- простое число.

Нам не известны простые числа $ r$, удовлетворяющие одновременно двум условиям

  $\displaystyle 2^{r-1}\equiv 1\mkern5mu({\rm mod}\,\,r^2),$ (6)
  $\displaystyle (r-1)/2$ -- простое число$\displaystyle .$ (7)

Среди простых чисел $ r<2,5\cdot10^9$ имеется лишь два числа 1093 и 3511, удовлетворяющих условию (6). Условие (7) для них, конечно же, нарушается. Тем не менее мы не должны исключать возможность составного числа $ M=r^2$ при $ 2q+1<k\leqslant 4q+2$, хотя эта возможность и маловероятна.

Изменим пункт 8 Алгоритма, добавив в него проверку условия $ M\ne(2p_{m+1}+1)^2$.

Так как при любом $ m$ справедливо неравенство $ t_m\leqslant 2t_{m+1}+1$, то при выполнении условий пункта  8 Алгоритма будем иметь

$\displaystyle 2k=N+u=\frac{p_m-1}{p_{m+1}}<2^{t_m-t_{m+1}+1}=2^{t_{m+1}+2}<8p_{m+1}. $

Это означает выполнимость всех условий следствия из теоремы 9. Но тогда можно утверждать простоту числа $ p_m$.

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

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