176 Глава 14. ТЕСТЫ СОЛОВЕЯ-ШТРАССЕНА И РАБИНА-МИЛЛЕРА ПРОВЕРКИ ЧИСЕЛ НА ПРОСТОТУ

При тестировании чисел на простоту с помощью вероятностного теста, основанного на малой теореме Ферма, может возникнуть ситуация, когда вероятность ошибки не снижается с количеством повторений теста. В подобном случае упомянутая вероятность равна единице и в результате тестирования может быть принято неверное решение. В этой связи разработаны и применяются на практике вероятностные тесты, свободные от указанного недостатка.

Примерами таких тестов являются тест Соловея-Штрассена [50] и тест Рабина-Миллера [51,52] проверки чисел на простоту. См. также [8,15,16].

14.1. Тест Соловея-Штрассена

На основании следующей теоремы в тесте Соловея-Штрассена используется критерий Эйлера для определения значения символа Лежандра (квадратичного характера числа по простому модулю).

В самом тесте, естественно, вычисляется символ Якоби по модулю n .

Теорема [16]. Нечетное целое число n является простым тогда и только

тогда,			когда для всех чисел a: 1≤ a ≤ n −1 выполняется сравнение вида
	n−1		a

a 2 = mod n .n

Назовем указанное сравнение соотношением Эйлера.

Доказательство. Если n простое, то данное сравнение, очевидно, выполнено в силу свойств символа Лежандра.

n−1	a					, 1≤ a ≤ n −1, но n составное.
Пусть теперь a 2	=		mod n
	n
		n−1			n−1	2	a 2
					2
В любом случае,	a						= =1mod n , поэтому n			- число
				= a
							n

Кармайкла, т.е. n = p1 p2 Kpk , k > 2 , pi ≠ pj для i ≠ j и i ϕ(pi )|(n −1).

Тест Соловея-Штрассена 177

Выберем элемент b, не являющийся квадратичным вычетом по модулю p1 . По китайской теореме об остатках, существует число a, удовлетворяющее

системе сравнений: a =b(p1 ), a =1(p2 ), K, a =1(pk ).

a

a

a

a

b

=

=

=

= −1

По определению символа Якоби,

,

p

K

p

p

p

n

1

k

1

1

n−1

a

следовательно, по условию, a 2

=

mod n = −1mod n .

n

Последнее сравнение выполняется по любому делителю n, следовательно,

n−1

(n −1) 2

делится на ϕ(p2 ) -

a 2 = −1mod p2 . Однако это не так,

поскольку

противоречие.

14.1.1. Эйлеровы псевдопростые числа

Составное число n, удовлетворяющее соотношению Эйлера, называется эйлеровым псевдопростым по основанию a.

Из доказанного следует, что составных чисел, которые были бы эйлеровыми псевдопростыми по любому основанию, не существует.

Следовательно, мы можем предложить следующий тест, аналогичный тесту Ферма.

Псевдослучайно выбираем вычет a {2,K,n −1}, проверяем условие

(a,n)=1. Если условие не выполнено, значит, n - составное. Проверяем соотношение Эйлера. Если оно не выполняется, то число n - составное. Иначе, повторяем тест для другого значения a.

Если мы могли бы проверить соотношение Эйлера для всех a, то мы смогли бы точно определить, является ли число n простым. Но для больших n это невозможно. Поэтому необходимо оценить, как ведет себя вероятность ошибки при увеличении числа k повторений теста.