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

Тест Соловея — Штрассена — вероятностный тест простоты, открытый в 1970-х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном. Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью он может дать неверный ответ. Основное преимущество теста заключается в том, что он, в отличие от теста Ферма, распознает числа Кармайкла как составные.

История

В 17 веке Ферма доказал утверждение, названное позже малой теоремой Ферма, служащее основой теста Ферма на простоту:

Если n — простое и a не делится на n, то $a^{n-1}\equiv 1(\mathrm{mod}n)$.

Эта проверка для заданного n не требует больших вычислений, однако утверждение, обратное этому, неверно. Так, существуют числа Кармайкла, являющиеся составными, для которых утверждение, приведенное в малой теореме Ферма, выполняется для всех целых чисел взаимнопростых с заданным числом. В 1994 году было показано, что таких чисел бесконечно много. В связи с обнаруженным недостатком теста Ферма, актуальность приобрела задача увеличения достоверности вероятностных тестов. Первым тест, отсеивающий числа Кармайкла как составные, предложил Леманн. Этот недостаток отсутствует также в тестах Соловея — Штрассена и Миллера — Рабина за счет более сильного критерия отсева, чем малая теорема Ферма. Независимо от друг друга Д. Лемер в 1976 году и Р. Соловей совместно с Ф. Штрассеном в 1977 году доказали, что аналога чисел Кармайкла, которые являются составными и одновременно эйлеровыми псевдопростыми, нет.Шаблон:Sfn На основе этого и был предложен тест Соловея — Штрассена на простоту, он был опубликован в 1977 году, дополнения к нему в 1978 году.

Обоснование

Тест Соловея — Штрассена опирается на малую теорему Ферма и свойства символа Якоби Шаблон:Sfn:

• Если n — нечетное составное число, то количество целых чисел a, взаимнопростых с n и меньших n, удовлетворяющих сравнению $a^{(n-1)/2}\equiv \left(\frac{a}{n}\right)(\mathrm{mod}n)$, не превосходит $\frac{n}{2}$.

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

Алгоритм Соловея — Штрассена

Алгоритм Соловея — Штрассена Шаблон:Sfn параметризуется количеством раундов k. В каждом раунде случайным образом выбирается число a < n. Если НОД(a,n) > 1, то выносится решение, что n составное. Иначе проверяется справедливость сравнения $a^{(n-1)/2}\equiv \left(\frac{a}{n}\right)(\mathrm{mod}n)$. Если оно не выполняется, то выносится решение, что n — составное. Если это сравнение выполняется, то a является свидетелем простоты числа n. Далее выбирается другое случайное a и процедура повторяется. После нахождения k свидетелей простоты в k раундах выносится заключение, что n является простым числом с вероятностью $1-2^{-k}$ .

На псевдокоде алгоритм может быть записан следующим образом:

 Вход: $n$ > 2, тестируемое нечётное натуральное число;
      $k$, параметр, определяющий точность теста.
Выход: составное, означает, что $n$ точно составное;
       вероятно простое, означает, что $n$ вероятно является простым.

for i = 1, 2, ..., $k$:
   $a$ = случайное целое от 2 до $n-1$, включительно;
   если НОД(a, n) > 1, тогда:
       вывести, что $n$ — составное, и остановиться.
   если $a^{(n-1)/2}\equiv ̸\left(\frac{a}{n}\right)(\mathrm{mod}n)$, тогда: 
       вывести, что $n$ — составное, и остановиться.

иначе вывести, что $n$ —  простое  с вероятностью $1-2^{-k}$, и остановиться.

Пример применения алгоритма

Проверим число n = 19 на простоту. Выберем параметр точности k = 2.

 k = 1
 Выберем случайное число a = 11;  2 < a < n - 1
 Проверим условие НОД(a,n)>1
 НОД(11,19)=1; значит проверяем выполнение сравнения  $a^{(n-1)/2}\equiv \left(\frac{a}{n}\right)(\mathrm{mod}n)$  
 $r=\left(\frac{a}{n}\right)=\left(\frac{11}{19}\right)=1$
 $s=a^{(n-1)/2}=11^{(19-1)/2}(\mathrm{mod}19)=1$
 Получили, что $r=s$ поэтому переходим к следующей итерации

 k = 2
 Выберем случайное число a = 5;    2 < a < n - 1
 Проверим условие НОД(a,n)>1
 НОД(5,19)=1;  значит проверяем выполнение сравнения  $a^{(n-1)/2}\equiv \left(\frac{a}{n}\right)(\mathrm{mod}n)$  
 $r=\left(\frac{a}{n}\right)=\left(\frac{5}{19}\right)=1$
 $s=a^{(n-1)/2}=5^{(19-1)/2}(\mathrm{mod}19)=1$
 $r=s$  и это была последняя итерация, отсюда делаем вывод, что 19 - простое число с вероятностью $1-2^{-2}$

Вычислительная сложность и точность

• Точность по сравнению с другими вероятностными тестами на простоту (здесь k — число независимых раундов)

название теста	вероятность(что число составное)	примечания
Ферма	$2^{-k}$	не распознает числа Кармайкла как составные
Леманна	$2^{-k}$
Соловея — Штрассена	$2^{-k}$

• Теоретическая сложность вычислений всех приведенных в таблице тестов оценивается как $O({\log }^{3}n)$ .Шаблон:Sfn
• Алгоритм требует $O(k{\log }_{2}m)$ операций над длинными целыми числами.
• При реализации алгоритма, для снижения вычислительной сложности, числа a выбираются из интервала 0 < a < c < n, где c — константа равная максимально возможному значению натурального числа, помещающегося в одном регистре процессора.Шаблон:Sfn

Применение

Вероятностные тесты применяются в системах основанных на проблеме факторизации, например RSA или схема Рабина. Однако на практике степень достоверности теста Соловея — Штрассена не является достаточной, вместо него используется тест Миллера — Рабина. Более того, используются объединенные алгоритмы, например пробное деление и тест Миллера — Рабина, при правильном выборе параметров можно получить результаты лучше, чем при применении каждого теста по отдельности.

Улучшение теста

В 2005 году на Международной конференции Bit+ «Informational Technologies −2005» А. А. Балабанов, А. Ф. Агафонов, В. А. Рыку предложили модернизированный тест Соловея — Штрассена. Тест Соловея — Штрассена основан на вычислении символа Якоби, что занимает время эквивалентное ${\log }_{2}n$. Идея улучшения состоит в том, чтобы в соответствии с теоремой квадратичной взаимности Гаусса, перейти к вычислению величины $\left(\frac{n}{a}\right)$,являющейся обратной символу Якоби, что является более простой процедурой..

См. также

• Псевдопростое число

Литература

1. Шаблон:Книга
2. Шаблон:Книга
3. Шаблон:Книга Шаблон:Wayback
4. Шаблон:Книга Шаблон:Wayback