8.2. Тест Соловея-Штрассена и Эйлеровы псевдопростые числа

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

В подобном случае упомянутая вероятность равна единице и в результате тестирования может быть принято неверное решение.

В этой связи, разработаны и применяются на практике вероятностные тесты, свободные от указанного недостатка.

Примерами таких тестов являются тест Соловея-Штрассена и тест Рабина-Миллера [18] проверки чисел на простоту.

В тесте Соловея-Штрассена используются свойства т.н. символов Лежандра и Якоби, связанных с разрешимостью двучленных квадратичных соавнений. Напомним вкратце их свойства.

Двучленным квадратичным сравнением называется сравнение вида , где- неизвестный вычет.

Целое число называется квадратичным вычетом по модулю, если сравнениеразрешимо. Если сравнение разрешимо, то для составного нечетного модуля количество решений, как правило, больше двух.

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

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

Существует эффективный алгоритм для определения, является ли данное число квадратичным вычетом по простому нечетному модулю или нет. Этот алгоритм позволяет вычислить, практически вручную, т.н. символ Лежандра, значение которого приравно 1, если- квадратичный вычет, и (-1) – в противном случае. Дляполагается.

С появлением компьютеров значение обычно вычисляется, исходя из соотношения:, которое является важным свойством символа Лежандра.

Если нечетное число факторизовано:, то разрешимость сравненияэквивалентна разрешимости всех сравнений вида.

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

Поэтому значение можно вычислить через величины.

С символом Лежандра тесно связан символ Якоби числапо модулю. Символ Якоби определяется для нечетных, взаимно простых чисел как произведение значений символов Лежандра:.

Он обладает практически всеми теми же свойствами, что и символ Лежандра, но по значению символа Якоби равному единице, нельзя утверждать, что соответствующий вычет – квадратичный. Для квадратичного вычета, тем не менее, символ Якоби равен единице. Следовательно, если, то- квадратичный невычет по модулю.

Эта особенность связана с тем, что соотношение не обязательно выполняется для символа Якоби, т.е, когда число(модуль) не является простым. Для нас символ Якоби важен потому, что его можно вычислить без факторизации модуля.

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

Теорема [17]. Нечетное целое число является простым тогда и только тогда, когда для всех чиселвыполняется соотношение Эйлера:.

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

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

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

Псевдослучайно выбираем вычет и проверяем условие. Если условие не выполнено, значит,– составное.

Проверяем соотношение Эйлера. Если оно не выполняется, то число – составное. Иначе, повторяем тест для другого значения.

Если мы могли бы проверить соотношение Эйлера для всех значений , то мы смогли бы точно определить, является ли числопростым.

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

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

Интересно, что эйлеровы псевдопростые являются псевдопростыми числами.

Теорема [17]. Пусть – нечетное составное число. Тогда:

а) если – эйлерово псевдопростое по основанию, то оно – псевдопростое по основанию;

б) если – эйлерово псевдопростое по основаниями, то– эйлерово псевдопростое по основаниями;

в) множество является подгруппой группы;

г) если не является эйлеровым псевдопростым по основанию, хотя бы для одного числа, то.

Таким образом, при повторении теста Соловея-Штрассена раз, вероятность неотбраковки составного числа не превосходит.