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

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