Теорема Диемитко и процедура генерации простых чисел заданной длины ГОСТ Р 34.10-94.

Следующая теорема позволяет строить доказуемо простые числа большего размера на основе простых чисел меньшего размера.

Теорема Диемитко.

Пусть n=qR+1, где q – простое число, R – четное, R<4(q+1).

Если найдется a<n: 1) a^n—1≡1(mod n); 2) 1(mod n), то n – простое число.

■

Итак, если имеем простое число q, то, перебирая четные числа R, строим числа n=qR+1 и испытываем их на простоту согласно теореме Диемитко, пока не получим простое число. По полученному числу можно построить еще одно простое число и т.д.

Приведем алгоритм перехода от меньшего простого числа q: |q|= к большему p: |p|=t, использующийся в ГОСТе. Фигурирующая в процедуре ξ есть равномерно распределенная на (0,1) случайная величина, получаемая с помощью линейного конгруэнтного генератора. Каждый раз на Шаге 1 получают новое значение ξ.

Алгоритм перехода от меньшего простого числа к большему:

Вход: t – требуемая размерность простого числа, q – простое число : |q|= .

Ш.1. Вычисляем N= . Если N – нечетное, то N=N+1.

Ш.2. u=0.

Ш.3. Вычисляем p=(N+u)q+1 – кандидат в простые.

Ш.4. Если p>2^t, возвращаемся на Ш.1.

Ш.5. Если 2^n—1≡1(mod n) и 2^N+u 1(mod n), то идем на Выход.

Ш.6. Вычисляем u=u+2. Возвращаемся на Ш.3.

Выход. p – простое число.

Первое слагаемое в построении числа N обеспечивает минимальный требуемый размер числа p, а второе вносит в процедуру поиска новых простых чисел необходимый элемент случайности.

Проверка на Шаге 4 необходима, чтобы число p не превышало своей верхней границы, а проверка на Шаге 5 есть проверка условия теоремы Диемитко при a=2.

Пример:

Вход: t=4, q=3=[11]₂

1. N= =3. N=N+1=4.

2. u=0.

3. p=4·3+1=13.

4. 13<2⁴=16.

5. 2¹² mod 13 =1, 2⁴ mod 13 = 3.

Выход. р=13=[1011]₂

Замечание

Поскольку на Шаге 5 условие теоремы Диемитко проверяется не для всех a<p, а только для 2, то некоторые простые числа, сгенерированных этим алгоритмом, не опознаются как простые. Но вероятность того, что для простого числа n наугад выбранное число a будет удовлетворять условиям теоремы Диемитко, есть (1—1/q), а q – достаточно большое число. Таким образом, проверки при a=2 вполне достаточно, чтобы не отсеивать слишком много простых чисел. Выбор a=2 обусловлен тем, что возведение числа 2 в степень в двоичном представлении является простой операцией.