Детерминированный тест, основанный на Теореме Димитко 185

Следовательно, p2 ≥ (F +1)2 > (R +1)(F +1)> FR +1 = n , т.е. p > n ,

что невозможно. Теорема доказана.

Если R >1,	то, поскольку	n = FR +1>1, неравенство	1 < R < F
выполняется при	F > n .	Поэтому предварительную	частичную

факторизацию числа n −1 следует проводить лишь до тех пор, пока F ≤ n .

15.2. Детерминированный тест, основанный на теореме Димитко

Рассмотрим еще один детерминированный тест, основой которого является т.н. теорема Димитко. В этой теореме вместо условия НОД(a(n−1)q −1, n)=1,

используемого в обобщенном критерии Люка, используется условие

a(n−1)q ≠1(n).

Лемма. Пусть n = qk R +1 >1, где q		-	простое,	не делящее R . Если
существует целое a такое, что	an−1 =1(n)	и	a(n−1) q	≠1(n), то существует
простой делитель p числа n вида	p = qk r +1, при некотором r = r(p).

m

Доказательство. Пусть n = ∏pimi . Поскольку a(n−1)q ≠1(n), то не все

i=1

делители n делят a(n−1)q −1. Поэтому, в силу китайской теоремы об остатках,

существует i : an−1 =1(pimi ), но a(n−1)q ≠1(pimi ). Следовательно, порядок t

элемента a по модулю pimi делит n −1 и не делит (n −1)q . Поэтому qk |t .

Известно, что группа классов вычетов, обратимых по модулю pimi , имеет первообразный элемент (циклична). Ее порядок равен ϕ(pimi )= pimi −1(pi −1).

186 Глава 15. ПОСТРОЕНИЕ БОЛЬШИХ ПРОСТЫХ ЧИСЕЛ

Этот порядок должен делиться на t и, следовательно, на qk . Поскольку q

делит n −1, а p	делит n, то q	и	p взаимно просты. Значит, qk |(p −1), т.е.
i			i	i
p = p = qk r +1.
i
Теорема (Димитко). Пусть n = qR +1 >1, где q - простое,				R - четное и
R < 4(q +1). Если существует целое a такое, что an−1 =1(n) и				a(n−1) q ≠1(n),

то число n - простое.

	m
Доказательство. Пусть n - составное, n = ∏piai . По условию, n = qh R1 +1,
	i=1
где h ≥1 и	q не делит R1 . Лемма показывает, что существует i , такое, что
q |(pi −1).	Таким образом, n =1(q) и pi =1(q). Запишем n в виде n = piu .

Очевидно, u =1(q), поэтому, u =1+ Kq и pi =1+ Sq .

Заметим, что K, S ≥ 2 . Действительно, n - нечетно, поскольку R - четное число. Если K = 0, то n - простое, что по допущению неверно. Если K =1, то n - четно, т.к. u четно.

Если S = 0 , то pi =1, что противоречит допущению. Если S =1, то pi -

четно, что также невозможно. Итак, u ≥ 2q +1, pi ≥ 2q +1, следовательно, n = piu ≥ (2q +1)2 = 4q(q +1)+1 > qR +1 = n - противоречие.

Теорема Димитко позволяет строить большие доказуемо простые числа.

Пусть дано некоторое число q , о котором известно, что оно простое.

Выберем R - четное число, разрядность которого равна разрядности q . В этом случае, очевидно, R < 4(q +1).

Детерминированный тест, основанный на Теореме Димитко 187

Построим n = qR +1. Если существует целое a, такое, что an−1 =1(n) и a(n−1)q ≠1(n), то число n - простое по теореме Димитко. Разрядность n в два раза больше разрядности числа q .

Если мы в качестве q примем построенное число n, то можем построить следующее простое число, вдвое большей разрядности, чем n и т.д.

Данный подход лежит в основе алгоритма генерации простых чисел в межгосударственном стандарте на цифровую подпись ГОСТ 34.310-95, широко используемом в Украине.