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

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

История


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

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

Обоснование


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

  • Если n — нечетное составное число, то количество целых чисел a, взаимнопростых с n и меньших n, удовлетворяющих сравнению a(n1)/2(an)(modn), не превосходит n2.

 Составные числа n удовлетворяющие этому сравнению называются псевдопростыми Эйлера-Якоби по основанию a.
  выполнено сравнение a(n1)/2(an)(modn)
 \texttt an1=(a(n1)/2)2=(an)2\\\texttt (an)2=1\texttt Отсюда следует an1=1(modn)\\\texttt Получаем, что  \textttn\texttt— число Кармайкла, поэтому   n=p1p2..pk\texttt  где pi\texttt - простое i = 1,2, ...k\\\texttt Рассмотрим \textttb\texttt такое, что  (bp1)=1(modn)\texttt \\\texttt Найдем такое  \texttta\texttt , что 
a={b(modp1),if i= 11(modpi),if i = 2,...,k
\\\texttt Такое \textttа\texttt  существует по китайской теореме об остатках и принадлежит Zn\texttt, так как является взаимно простым с \textttn\texttt.\\\texttt (an)=(ap1)(ap2)....(apk)=(ap1)=(bp1)=1\\a(n1)/2(an)(modn)\\(an)=1\texttt  Отсюда a(n1)/2 1(modn)\\a(n1)/2 1(modp1)\\a(n1)/2 1(modp2)\texttt   противоречие с тем, что a 1(modpi)\\\textttЗначит неверно наше предположение о том, что  \textttn\texttt -   составное.

  • Доказательство того, что количество таких чисел не превосходит n/2 можно найти в любом пособии по теоретико-числовым алгоритмам.

 \}\}

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


 Алгоритм Соловея — Штрассена параметризуется количеством раундов k. В каждом раунде случайным образом выбирается число a \textless n. Если НОД(a,n) \textgreater 1, то выносится решение, что n составное. Иначе проверяется справедливость сравнения a(n1)/2(an)(modn). Если оно не выполняется, то выносится решение, что n — составное. Если это сравнение выполняется, то a является свидетелем простоты числа n. Далее выбирается другое случайное a и процедура повторяется. После нахождения k свидетелей простоты в k раундах выносится заключение, что n является простым числом с вероятностью 12k .
 На псевдокоде алгоритм может быть записан следующим образом:
 \texttt \textttВход\texttt: n\texttt \textgreater 2, тестируемое нечётное натуральное число;\\\texttt      k\texttt, параметр, определяющий точность теста.\\\textttВыход\texttt: \textttсоставное\texttt, означает, что n\texttt точно составное;\\\texttt       \textttвероятно \textttпростое\texttt, означает, что n\texttt вероятно является простым.\\\\\textttfor\texttt \texttti\texttt = 1, 2, ..., k\texttt:\\\texttt   a\texttt = случайное целое от 2 до n1\texttt, включительно;\\\texttt   \textttесли\texttt НОД(a, n) \textgreater 1, \textttтогда\texttt:\\\texttt       \textttвывести\texttt, что n\texttt — составное, и \textttостановиться\texttt.\\\texttt   \textttесли\texttt a(n1)/2(an)(modn)\texttt, \textttтогда\texttt: \\\texttt       \textttвывести\texttt, что n\texttt — \textttсоставное\texttt, и \textttостановиться\texttt.\\\\\textttиначе \textttвывести\texttt, что n\texttt — '' простое  с вероятностью 12k\texttt'', и \textttостановиться\texttt.

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


 Проверим число n = 19 на простоту. Выберем параметр точности k = 2.
 \texttt k = 1\\\texttt Выберем случайное число \texttta\texttt = 11;  2 \textless a \textless n - 1\\\texttt Проверим условие НОД(a,n)\textgreater1\\\texttt НОД(11,19)=1; значит проверяем выполнение сравнения  a(n1)/2(an)(modn)\texttt  \\\texttt r=(an)=(1119)=1\\\texttt s=a(n1)/2=11(191)/2(mod19)=1\\\texttt Получили, что r=s\texttt поэтому переходим к следующей итерации
 \texttt k = 2\\\texttt Выберем случайное число \texttta\texttt = 5;    2 \textless a \textless n - 1\\\texttt Проверим условие НОД(a,n)\textgreater1\\\texttt НОД(5,19)=1;  значит проверяем выполнение сравнения  a(n1)/2(an)(modn)\texttt  \\\texttt r=(an)=(519)=1\\\texttt s=a(n1)/2=5(191)/2(mod19)=1\\\texttt r=s\texttt  и это была последняя итерация, отсюда делаем вывод, что 19 - простое число с вероятностью 122

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



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

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


  • Теоретическая сложность вычислений всех приведенных в таблице тестов оценивается как O(log3n) .
  • Алгоритм требует O(klog2m) операций над длинными целыми числами.
  • При реализации алгоритма, для снижения вычислительной сложности, числа a выбираются из интервала 0 \textless a \textless c \textless n, где c — константа равная максимально возможному значению натурального числа, помещающегося в одном регистре процессора.

Применение


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

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


 В 2005 году на Международной конференции Bit+ «Informational Technologies −2005» А. А. Балабанов, А. Ф. Агафонов, В. А. Рыку предложили модернизированный тест Соловея — Штрассена. Тест Соловея — Штрассена основан на вычислении символа Якоби, что занимает время эквивалентное log2n. Идея улучшения состоит в том, чтобы в соответствии с теоремой квадратичной взаимности Гаусса, перейти к вычислению величины (na),являющейся обратной символу Якоби, что является более простой процедурой..