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

13.7.4 Распознает ли Алгоритм все простые числа?

Основное время в процессе работы Алгоритма уходит на поиск простых чисел в прогрессии $ 2kq+1$. Если Алгоритм наткнулся на такое число, то проверка простоты его, в случае справедливости условий теоремы 8, выполняется сравнительно быстро. Поэтому важным качеством алгоритма должна быть способность доказывать простоту каждого простого числа, встречающегося в прогрессии.

Отметим, в этой связи, что не все простые числа $ p=2kq+1$ могут быть распознаны указанным алгоритмом. Другими словами, перебирая последовательно четные числа $ N+u$, и проверяя числа $ p=(N+u)p_{m+1}+1$ на простоту, Алгоритм может не распознать некоторые простые числа $ p$ и, увеличив значение $ u$, продолжать работу дальше. Это, конечно, может приводить к увеличению времени работы алгоритма. Укажем некоторые примеры чисел $ p$, не идентифицируемых Алгоритмом как простые. Простыми являются все числа $ M$ из следующего списка:     1) $ M=13367=1+82\cdot163$, $ q=163$, $ 2^{41}\equiv 1\mkern5mu({\rm mod}\,\,M)$;

    2) $ M=121369=1+312\cdot389$, $ q=389$, $ 2^{39}\equiv 1\mkern5mu({\rm mod}\,\,M)$;

    3) $ M = 122921 = 1+280\cdot439$, $ q=439$, $ 2^{35}\equiv 1\mkern5mu({\rm mod}\,\,M)$;

    4) $ M = 649657 = 1+504\cdot1289$, $ q=1289$, $ 2^{63}\equiv 1\mkern5mu({\rm mod}\,\,M)$;

    5) $ M=3203431780337=1+397424\cdot8060489$, $ q=8060489$, $ 2^{59}\equiv 1\mkern5mu({\rm mod}\,\,M)$.

Во всех указанных случаях $ M=2kq+1$ и имеют место сравнения

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

Значит, если одно из указанных чисел $ q$ встретится в Алгоритме как $ p_{m+1}$, а соответствующие значения $ 2k$ будут равны $ N+u$, то числа $ M$ не будут приняты как простые $ p_m$ и Алгоритм продолжит работу.

Указанные примеры являются частными реализациями при $ a=2$ следующего общего утверждения.

Предложение 1.  Пусть $ M=2kq+1$ -- простое число, причем $ q$ простое и $ 2k\leqslant q-1$. Если $ a\in\mathbb{Z}$, $ M\nmid a$, и порядок числа $ a$ по модулю $ M$ не превосходит $ \sqrt M$, то $ a^{2k}\equiv 1\mkern5mu({\rm mod}\,\,M)$ и, следовательно, простое число $ M$ не удовлетворяет условиям теоремы 8.

Исключить указанный пропуск простых чисел можно за счет проверки в Алгоритме условий теоремы 8 не только при $ a=2$, но и при других значениях основания $ a$.

Предложение 2.  Для каждого простого числа $ M=2kq+1$, $ q\geqslant 5$, $ k\leqslant 4q+2$, на промежутке $ 2\leqslant a\leqslant M-1$ имеется не менее $ M-1-3\sqrt M$ чисел $ a$, для которых выполнены условия теоремы 8.

Предложение 2 показывает, что, выбирая случайным образом числа $ a$ на промежутке $ 2\leqslant a\leqslant M-1$ при простом $ M$, можно с вероятностью, большей чем $ 1-O(M^{-1/2})$, найти число $ a$, для которого будут выполнены условия теоремы 8.

Удобнее, однако, выбирать числа $ a$ последовательно: $ a=2,3,\ldots$. Увеличение продолжительности работы при этом произойдет лишь для тех простых чисел $ M$, которые пропускались Алгоритмом. Но и для них, если принять на веру, что корни сравнения $ x^{2k}\equiv 1\mkern5mu({\rm mod}\,\,M)$ распределены равномерно на промежутке $ 1\leqslant x\leqslant M-1$, необходимое для выполнимости теоремы 8 число $ a$ будет найдено, согласно предложению 2, достаточно быстро.

Но как будет работать измененный алгоритм, если число $ p_m$ составное? Существуют составные числа $ M$ (числа Кармайкла) для которых условие (2) выполняется при любом $ a$, $ (a,M)=1$, так же как и для простых чисел. Эти числа встречаются достаточно редко. Тем не менее в 1993 г. доказано, что их бесконечно много. Известна модификация теста теоремы 8, основанная на следующей теореме:

Теорема 10 ([Rab], [Will]).  Пусть M -- нечетное составное число, $ M-1=2^sd$, $ d$ нечетно, и $ W(M)$ -- множество натуральных чисел $ a$, $ 1<a<M$, для которых выполнены условия:     1) $ a^d\not\equiv 1\mkern5mu({\rm mod}\,\,M)$,

    2) при всех $ i$, $ 0\leqslant i\leqslant s-1$

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

Тогда количество элементов в $ W(M)$ не меньше $ 3(M-1)/4$.

Если $ M$ -- простое число, то для каждого $ a$, $ 1<a<M$, согласно малой теореме Ферма имеем

$\displaystyle M\mid(a^{M-1}-1)=(a^d-1)(a^d+1)(a^{2d}+1)\cdot\ldots\cdot(a^{2^{s-1}d}+1), $

т. е. для простого $ M$ хотя бы одно из условий теоремы 10 обязательно нарушается. В то же время, как следует из теоремы 9, для составного числа $ M$ нарушение хотя бы одного из условий теоремы 9 происходит с вероятностью $ \leqslant 1/4$ при случайном выборе $ a$ на интервале $ 1<a<M$. При этом, что легко видеть, выполняется сравнение (2). Таким образом, если проверять для числа $ M$ выполнимость условий 1) и 2) для $ k$ случайно выбранных значений $ a$, или, что технически удобнее, для $ a=2,3,\ldots,k+1$, то с вероятностью, большей, чем $ 1-4^{-k}$, составное число $ M$ будет при этом опознано как составное.

Итак, изменим пункт 8 Алгоритма следующим образом:   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}\,\,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. Положить $ u\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-4mu}=u+2$ и перейти в пункт 6.

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

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

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

  8.7. Проверить условие $ 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$.

Как уже было сказано, приведенное выше изменение пункта 8 Алгоритма позволит достаточно быстро доказывать как простоту числа $ p_m$, если оно простое, так и непростоту, если оно составное. При простом $ p_m$ Алгоритм из пунктов 8.3 и 8.4 будет всегда переходить в пункт 8.6, и согласно предложению 2 довольно быстро будет найдено число $ a$, для которого выполнится условие (8). Условие пункта 8.7 для простого числа $ p_m$, конечно же, будет выполнено. Так что Алгоритм попадет в пункт 8.8, а затем перейдет к построению простого числа $ p_{m-1}$. Если же число $ p_m$ составное и нарушается хотя бы одно из условий пунктов 8.3 и 8.4, то согласно следствию из теоремы 9 для $ p_m$ не могут выполняться оба условия пунктов 8.6 и 8.7. Но тогда Алгоритм перейдет в пункт 8.2, будет вычислено новое значение $ a$, с которым будут проверяться условия пунктов 8.3 и 8.4. Согласно теореме 10 довольно быстро будет обнаружено число $ a$, для которого будут выполнены условия пунктов 8.3 и 8.4. Тогда число $ p_m$ будет определено как составное и из пункта 8.6 Алгоритм перейдет к построению нового числа $ p_m$.

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

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