2.10. Генерация простых чисел в Российском стандарте выработки электронной цифровой подписи ГОСТ Р34.10 – 94

Метод основан на теореме Диемитко.

Теорема Диемитко (1988 г.)

Пусть n = q R + 1, где q – простое. Тогда если существует целое a такое, что:

1)   aⁿ – 1 = 1 (mod n)       и

2)   a^{(n – 1) / q} ≠ 1 (mod n),

то найдется простой делитель p числа n, для которого верно условие p = 1 (mod q).

Доказательство.

Пусть  Из первого условия можно записать: для  любого i = 1, …, k, откуда следует, что Из второго условия следует, что найдётся j, для которого Значит, . Следовательно, имеет место делимость Но в силу условия (q, n) = 1 выполнено также поэтому q | p_j – 1, или p_j = 1 (mod q). Теорема доказана.

Следствие. Если, в условиях теоремы Диемитко, R – чётное и R < 4 (q +1), то n – простое.

Доказательство.

Предположим, что n = q R  + 1 – составное, p_j – его делитель такой, что p_j = 1 (mod q), и n = p_j · Q. Из условий p_j = 1 (mod q) и n = 1 (mod q) следует Q = 1 (mod q); из чётности R следует нечётность n, а значит, нечётность p_j и Q, что влечёт выполнение неравенств p_j ≥ 1 + 2q и Q ≥ 1 + 2q. Можем записать:

n = p_j · Q ≥ (1 + 2q)² = q · 4(q + 1) + 1 > q · R + 1 = n.

Полученное противоречие доказывает следствие.