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

Это можно сделать, исходя из утверждения, аналогичного тому, которое мы рассматривали при анализе свойств псевдопростых чисел. Интересно, что

эйлеровы псевдопростые являются псевдопростыми числами.
Теорема [16]. Пусть n - нечетное составное число. Тогда:
а) если n - эйлерово псевдопростое по основанию a, то оно псевдопростое
по основанию a;
б)	если n - эйлерово псевдопростое по основаниям a и b, то n - эйлерово
псевдопростое по основаниям ab и ab−1(modn);
					(n−1) 2	a
в)	множество		En = a Zn	: a		=		(mod n) является подгруппой
						n
группы	F ={a Z	n	: an−1 =1(mod n)};
	n

г) если n не является эйлеровым псевдопростым по основанию a, хотя бы для одного числа a, то En ≤ (1 2)Zn* .

Действительно, свойства а), б) и в) следуют из мультипликативности символа Якоби и того факта, что его значение равно ±1.

Докажем г): En ≤ Fn ≤ (1 2)Zn* .

Таким образом, при повторении теста Соловея-Штрассена k раз,

вероятность неотбраковки составного числа ≤ (12)k .

14.2. Тест Рабина-Миллера

Еще более эффективным тестом является тест Рабина-Миллера, в котором используется критерий, в конечном счете основанный на факте, что для простого модуля квадратными корнями из единицы являются лишь числа ±1,

а для составного нечетного модуля n =uv , (u,v)=1, число таких корней больше двух.

2s−1t .

n −1 = 2s t ,

Тест Рабина-Миллера 179

Пусть n - нечетное натуральное число. Тогда можно записать где t - нечетное и s ≥1.

Если число n - простое, то an−1 =1(n), при (a,n)=1. Поэтому квадратные корни из единицы имеют вид: a(n−1)2 = ±1(n), где показатель равен

Это означает, что в ряду вычетов по модулю n чисел at , a2t ,Ka2s −1 t либо появится −1(n), либо все они сравнимы с единицей, т.е. at =1(n).

Если n - составное, то возможны и другие случаи.

Основанный на данном замечании тест Рабина-Миллера заключается в следующем:

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

(a,n)=1. Если условие не	выполнено, значит, n	- составное и работа
закончена;
2) вычисляем at (mod n).	Если at = ±1(mod n),	то не исключено, что

число n - простое и необходимо перейти на начало, чтобы повторить тест для другого основания;

3) вычисляем последовательно вычеты чисел a2t ,Ka2s −1 t по модулю n,

пока не появится (−1), либо не исчерпается список;

4)если (−1) обнаружена в списке, то не исключено, что число n - простое

инеобходимо перейти на начало, чтобы повторить тест для другого основания;

5)если ни одно число из списка не сравнимо с (−1), то число n - составное

инеобходимо закончить работу.

Как и для ранее рассмотренных тестов, существуют составные числа n, которые для соответствующих оснований a проходят тест.

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

14.2.1. Сильно псевдопростые числа

Назовем число n = 2s t +1, где s ≥1, t - нечетно, сильно псевдопростым по основанию a >1, если выполняется одно из двух условий: at = ±1(n), либо в

последовательности a2t ,Ka2s −1 t существует число, сравнимое с –1 по модулю n.

Оказывается, можно показать, что для любого a >1 существует бесконечно много сильно псевдопростых чисел n по основанию a. Пример: a =7 , n = 25; a=5, n=781.

Можно доказать следующие основные свойства сильно псевдопростых чисел [15]:

1)число n сильно псевдопростое по основанию a является эйлеровым псевдопростым по тому же основанию;

2)если нечетное составное число n является сильно псевдопростым по основанию a, то общее количество оснований, по которому это число является

сильно псевдопростым, не превышает (n −1)4 .

Таким образом, при повторении теста Рабина-Миллера k раз вероятность неотбраковки составного числа ≤ (14)k .

Оказывается, количество повторений теста, достаточное для практических

приложений, можно ограничить величиной 2log22 n .

Интересно отметить, что простоту небольших простых чисел можно проверять, используя несколько заранее указанных оснований.

Примеры [16]: если n<1373653 - сильно псевдопростое по основаниям 2 и 3, то n - простое; если n<341550071728321 - сильно псевдопростое по основаниям 2, 3, 5, 7, 11, 13, 17, то n - простое.