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

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

История

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

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

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

Обоснование

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

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

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

Доказательство ^[5]

• Докажем, что выполнения сравнения ${\displaystyle a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}}$ необходимо и достаточно для того, чтобы число n было простым.

 Необходимость следует из критерия Эйлера для символа Лежандра. 
 Для доказательства достаточности воспользуемся методом от противного.
 Предположим, что n — составное и при этом  для ${\displaystyle \forall a\in \mathbf {Z_{n}} }$   выполнено сравнение  ${\displaystyle a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}}$
 ${\displaystyle a^{n-1}=(a^{(n-1)/2})^{2}=\left({\frac {a}{n}}\right)^{2}}$
 ${\displaystyle \left({\frac {a}{n}}\right)^{2}=1}$ Отсюда следует ${\displaystyle a^{n-1}=1(modn)}$
 Получаем, что  n— число Кармайкла, поэтому   ${\displaystyle n=p_{1}p_{2}..p_{k}}$  где ${\displaystyle p_{i}}$ - простое i = 1,2, ...k
 Рассмотрим b такое, что  ${\displaystyle \left({\frac {b}{p_{1}}}\right)=-1(modn)}$ 
 Найдем такое  a , что :${\displaystyle a={\begin{cases}b(mod{p_{1}}),&{\mbox{if }}i{\mbox{= 1}}\\1(mod{p_{i}}),&{\mbox{if }}i{\mbox{ = 2,...,k}}\end{cases}}}$
 Такое а  существует по китайской теореме об остатках и принадлежит ${\displaystyle Z_{n}}$, так как является взаимно простым с n.
 ${\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_{2}}}\right)....\left({\frac {a}{p_{k}}}\right)=\left({\frac {a}{p_{1}}}\right)=\left({\frac {b}{p_{1}}}\right)=-1}$
${\displaystyle a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}}$
${\displaystyle \left({\frac {a}{n}}\right)=-1}$  Отсюда ${\displaystyle a^{(n-1)/2}\equiv \ -1(modn)}$
${\displaystyle a^{(n-1)/2}\equiv \ -1(modp_{1})}$
${\displaystyle a^{(n-1)/2}\equiv \ -1(modp_{2})}$   противоречие с тем, что ${\displaystyle a\equiv \ 1(modp_{i})}$
Значит неверно наше предположение о том, что  n -   составное.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Применение

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

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

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

См. также

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