§ 1.7. Вероятностные тесты на простоту

37

Это рассуждение завершает обоснование алгоритма Миллера и доказательство теоремы.

§ 1.7. Вероятностные тесты на простоту

Пусть n N, n нечетно, n > 1. Вероятностный тест на простоту проводится следующим образом. Выбирается случайное a N, 1 a < n, и для него проверяется выполнение некоторых условий. Если какоето из условий не выполнено, то число n — составное, поскольку для простых чисел эти условия являются необходимыми. Если же все условия выполнены, то из этого еще не следует простота n. Однако можно будет считать, что «n — простое число с некоторой вероятностью». Кроме того, обычно доказывают оценку снизу для этой вероятности. Чем больше значений a мы протестируем, тем ближе эта вероятность к единице.

Рассмотрим тест Соловея—Штрассена [262].

Теорема 1.53. Пусть n — нечетное составное число. Тогда количество целых чисел a, 0 a n − 1, удовлетворяющих условиям

	1)	(a, n) = 1,	a
	2)	a(n−1)/2 ≡		(mod n),
			n
		n 2.
	не превышает		/

Следствие 1.54. Если n — простое, то условия 1 и 2 теоремы, очевидно, выполняются для всех a, 1 a n − 1. Если же n —

составное,	то для случайно выбранного a из промежутка
0 a n − 1	вероятность выполнения обоих условий теоремы

не превосходит 1/2. Поэтому, если для k случайных значений a мы проверим выполнение условий теоремы и не обнаружим, что n — составное, то будем считать, что n — простое с вероятностью, не меньшей чем 1 − 1/2k.

Доказательство теоремы 1.53. Покажем сперва, что существу-

n−1

b

ет b N,

для которого

(b, n) = 1 и b 2

≡

(mod

n). Пусть n =

n

1

k

разложение

на простые сомножители.

= p1 . . . pk —

n

то найдется b N,

Если

n

делится на

квадрат простого

числа,

(b, n) = 1, такое, что bn−1 ≡ 1 (mod n),

n−1

≡ ±1 (mod n).

откуда

b

2

Действительно, фиксируем номер i

такой,

что

i 2.

По китайской

b N,

i

)

теореме

об

остатках можно найти

для

которого b (mod pij

является первообразным корнем в Z/pi i Z, а при j = i b ≡ 1 (mod pj ).

38 Гл. 1.

Тестирование чисел на простоту и построение больших простых чисел

n − 1

.

=

Если bn−1 ≡ 1 (mod n), то bn−1 ≡ 1 (mod pi i), откуда

.. (pi i)

= pi i−1 (pi − 1), что невозможно, так как n − 1 не делится на pi.

Предположим теперь,

что n

бесквадратно, n = p1 . . . pk.

Най-

дем такое

b N, что b (mod p1) — первообразный корень в Z/p1Z,

и b ≡ 1 (mod pj) при j > 1. Тогда (b, n) = 1 и

b

b

b

b

=

. . .

=

= −1.

n

p1

pk

p1

n−1

n−1

≡

Сравнение

b 2 ≡ −1

(mod

n)

равносильно

сравнению

b

2

n−1

≡ −1 (mod p2),

≡ −1 (mod pj) для j = 1, . . . , k. Так как k 2, то 1 ≡ b 2

что невозможно.

Итак, число b существует. Зафиксируем его и рассмотрим два мно-

жества:

n−1

a

W1 = a | 1 a n − 1,

(a, n) = 1,

an

2

≡

(mod n) ,

1

n

W2 = a | 1 a n − 1,

(a, n) = 1,

a

−2

≡

a

(mod n) ,

n

Если a1 W1, a2 W2, то a1a2 W2, поскольку

a1a2

=

a1

a2

.

n

n

n

Поэтому для каждого

a

W1 наименьший

неотрицательный

вычет

ba (mod n) принадлежит W2. Следовательно, |W2| |W1|, откуда вытекает утверждение теоремы.

Теперь рассмотрим более эффективный тест Миллера—Рабина (см. [230; 20]).

Теорема 1.55. Пусть n — нечетное составное число. Пусть 3 n, n − 1 = 2rt, где r 1, t — нечетно. Тогда количество таких чисел a, 0 < a n − 1, что либо at ≡ 1 (mod n), либо при некотором j, 1 j r,

a(n−1)/2j ≡ −1 (mod n),

не превосходит n/4.

Следствие 1.56. Из теоремы 1.55 аналогично следствию 1.54 получаем вероятностный тест на простоту. При этом, если для k случайных значений a мы не обнаружим, что n— составное, то будем считать, что n— простое с вероятностью, не меньшей чем 1 − 41k .

Замечание 1.57. Если	n	—	/	—	2	an−1	≡
			простое, то Z nZ		поле,

≡ 1 (mod n) для всех a, 1 a n − 1. Так как уравнение x ≡ 1 (mod n)

§ 1.7. Вероятностные тесты на простоту

39

имеет в Z/nZ ровно два решения ±1, то cравнения теоремы 1.55 выполнены для всех a, 1 a n − 1.

Замечание 1.58. Тест Миллера—Рабина всегда сильнее теста Соловея—Штрассена, как показано в работе [190]. Точнее, если при фиксированном n число a проходит тест Миллера—Рабина и не показывает, что n составное, то оно проходит тест Соловея—Штрассена с тем же результатом.

Замечание 1.59. В работе [13] показано, что некоторый аналог алгоритма Миллера—Рабина может быть применен для проверки простоты главных идеалов в круговых полях. В работе [17] показана возможность применения этого алгоритма в некоторых криптосистемах типа RSA.

Для доказательства теоремы 1.55 нам потребуется ряд лемм. Обо-

значим через S множество a (mod n), 1 a n, таких, что либо at ≡ 1 (mod n), либо при некотором j, 1 j r, a(n−1)/2j ≡ −1 (mod n). Мы считаем далее, что n — нечетное, составное, не делящееся на 3 число.

Лемма 1.60. Если существует простое число p такое, что p2 | n, то множество

	G = 1 + k pn (mod n) k = 0, . . . , p − 1
является подгруппой (Z/nZ) порядка						p.
Доказательство. Из сравнений
1 + p 1 +				p	≡ 1 + ((k + k ) (mod p)) p (mod n)
	kn		k n						n
и
	1 +	kn		l	≡ 1 + (kl (mod p))		n	(mod n)
		p					p

легко следует утверждение леммы.

Определение 1.61. Обозначим A множество элементов a (Z/nZ) , для которых выполнено одно из следующих двух условий:

1)an−1 ≡ 1 (mod n);

2)ak ≡ −1 (mod n) для любого k Z, и для некоторого простого p,

p | n, порядок a (mod p) равен p − 1.

Лемма 1.62. Пусть a A, s S. Тогда as S, т. е. aS ∩ S = .

Доказательство. Если an−1 ≡ 1 (mod n), то поскольку sn−1 ≡ ≡ 1 (mod n), получим (as)n−1 ≡ 1 (mod n), т. е. as S.

40 Гл. 1. Тестирование чисел на простоту и построение больших простых чисел

Пусть далее a не удовлетворяет первому, но удовлетворяет второму условию в определении множества A. Тогда an−1 ≡ 1 (mod n) и для любого целого k выполнено сравнение ak ≡ −1 (mod n). Также фиксируем простое число p, p | n, для которого порядок a (mod p) равен p − 1. Зафиксируем число i такое, что

a(n−1)/2i ≡ 1 (mod n).

Такие i существуют, например, i = 0. Кроме того, поскольку p | n, то

		a	(n−1)/2i		≡	1 (mod ).
						p
По условию тогда	n − 1	..		1, откуда в силу четности			p −	1 получаем
	2i	. p −
неравенство 0 i < r. В частности, отсюда следует,что

a(n−1)/2r = at ≡ 1 (mod n).

Покажем, что если s S, то при всех j таких, что 0 j i < r, выполнено сравнение

s	(n−1)	/2j	≡	1 (mod ).	(1.1)
				n

Если s S и s(n−1)/2r ≡ 1 (mod n), то сравнение (1.1) выполнено. Предположим теперь, что s S и для некоторого j1, 0 j1 r,

s(n−1)/2j1 ≡ −1 (mod n).

В случае j1 > i отсюда следует, что при всех j, 0 j i, выполнено сравнение

s(n−1)/2j ≡ 1 (mod n),

т. е. формула (1.1) верна.

Рассмотрим случай j1 i и придем к противоречию. Поскольку

s(n−1)/2j1 ≡ −1 (mod n),

то

s(n−1)/2j1 ≡ −1 (mod p).

§ 1.7. Вероятностные тесты на простоту											41
Кроме того, по предположению j1 i, откуда по доказанному выше
p −		1			2i				2j1
Из малой теоремы Ферма тогда следует,									что
s	(n−1)		/2j1		≡	1 (mod ).
									p
Это и есть противоречие, так как 1 ≡ −1 (mod p).
Итак, формула (1.1) верна. Далее, из (1.1) следует, что
s(n−1)/2i+1					≡ ±1 (mod n),

поскольку s S.

Теперь выберем i максимальным. Тогда, поскольку по доказанному i < r, имеем

a(n−1)/2i ≡ 1 (mod n), a(n−1)/2i+1 ≡ ±1 (mod n).

(Мы воспользовались тем, что ak ≡ −1 (mod n) для всех k Z.) Тогда при всех j, 0 j i, выполнено сравнение

(as)(n−1)/2j ≡ 1 (mod n),

но

(as)(n−1)/2i+1 ≡ ±a(n−1)/2i+1 ≡ ±1 (mod n),

Отсюда следует, что as S.

Лемма 1.63. Пусть a, b (Z/nZ) , a = b. Множества aS и bS не пересекаются тогда и только тогда, когда не пересекаются множества ab−1S и S.

Доказательство очевидно.

Следствие 1.64. Пусть G — подгруппа (Z/nZ) . Множества g1S и g2S не пересекаются при всех g1, g2 S, g1 = g2, тогда и только тогда, когда не пересекаются множества S и gS для всех g G, g = 1.

Лемма 1.65. Пусть n составное и n делится на p2, где p — простое число. Тогда

|S| 14 |(Z/nZ) |.

Доказательство. Пусть G — подгруппа (Z/nZ) из леммы 1.60. Поскольку p | n, то p n − 1, и тогда для любого g G, g = 1, выполнено сравнение gn−1 ≡ 1 (mod n). Поэтому g A и по лемме 1.62

42	Гл. 1.		Тестирование чисел на простоту и построение больших простых чисел
множества			S и gS	не пересекаются. Значит, по следствию лем-
мы	1.63	множества		gS, g G, попарно не пересекаются. Поэтому
g G Sg		= |G| · |S| = p|S|, и p|S| |(Z/nZ) | = (n), откуда
				|S|	(n)		1	|(Z/nZ) |,
					p		4

так как p 5 по условию теоремы. Лемма 1.65 доказана.

Лемма 1.66. Пусть n = p1p2, где p1 и p2 — различные простые числа. Тогда n − 1 не делится на одно из двух чисел pi − 1.

Доказательство следует из равенства

n − 1 = p1p2 − 1 = (p1 − 1) (p2 − 1) + (p1 − 1) + (p2 − 1).

Лемма 1.67. Пусть n = p1p2, где p1 = p2. Тогда |S| (n)/4.

Доказательство. По китайской теореме об остатках найдутся чис-

ла a1 и a2 такие, что ai ≡ 1 (mod p3−i), иkai

(mod pi) — первообразный

k

i ≡ −

1 (mod p

3−i

корень по модулю pi

для i = 1, 2. Тогда a

) для любого

k Z; кроме того, ai

≡ 1 (mod pi) тогда и только тогда, когда pi − 1 | k.

Это значит, что

. Очевидно также, что

−1 (mod

)

. Далее, для

элемента

ai A

) сравнение

k

ai

n

A

a ≡ a1a2

(mod

a ≡

1 (mod ) выполнено тогда

k

n

n

и только тогда, когда ai ≡ 1 (mod pi) для i = 1, 2, что равносильно усло-

вию p

i −

1

|

1

an−1

≡

1 (mod n),

k. Отсюда по лемме 1.66 получаем, что

т. е. a = a1a2 A. Аналогично a1a−2 A.

Рассмотрим теперь множества S, Sa1, Sa2, Sa. По леммам 1.62 и 1.63 они попарно не пересекаются. Кроме того, S, Sa1, Sa2, Sa содержатся в (Z/nZ) и состоят из одинакового количества элементов.

Поэтому |S| 14 |(Z/nZ) |.

Лемма 1.68. Пусть n бесквадратно и делится на три различ-

ных простых числа p1, p2, p3. Тогда |S| (n)/4.

Доказательство. Как и при доказательстве леммы 1.67, найдутся

a1, a2 (Z/nZ)

n

такие,

что

ai ≡ 1

mod

pi

, ai

(mod

pi) — перво-

образный корень по модулю

pi

,

i

= 1, 2.

Тогда

ai ≡

1

(mod

)

для

= 1, 2;

a1a2 = a ≡

1 (mod

−

1

p3

того

),

≡

1 (mod

). Кроме

i k

≡ −1

p3

b ≡ a1a2

p3

ai

(mod n)

для любого k Z (так как 1 ≡ −1

(mod p3)). Так-

же

a ≡ −

n

a = a1a2

и

b

≡ −

1 (mod

n

b = a1a2

k

1 (mod ) при

k

) при

−1.

Значит,

a1, a2, a, b A

(требование

о порядке элемента во

втором

условии из определения множества A выполнено по построению a1 и a2). По леммам 1.62 и 1.63 множества S, Sa1, Sa2, Sa попарно