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

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

История

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

Если n — простое и a не делится на n, то a n − 1 ≡ 1 ( mod n ) {displaystyle a^{n-1}equiv 1{pmod {n}}} .

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

Обоснование

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

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

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

Доказательство

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

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

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

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

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

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

Вход: n {displaystyle n} > 2, тестируемое нечётное натуральное число; k {displaystyle k} , параметр, определяющий точность теста. Выход: составное, означает, что n {displaystyle n} точно составное; вероятно простое, означает, что n {displaystyle n} вероятно является простым. for i = 1, 2, ..., k {displaystyle k} : a {displaystyle a} = случайное целое от 2 до n − 1 {displaystyle n-1} , включительно; если НОД(a, n) > 1, тогда: вывести, что n {displaystyle n} — составное, и остановиться. если a ( n − 1 ) / 2 ≢ ( a n ) ( mod n ) {displaystyle a^{(n-1)/2} ot equiv left({a over n} ight){pmod {n}}} , тогда: вывести, что n {displaystyle n} — составное, и остановиться. иначе вывести, что n {displaystyle n} — простое с вероятностью 1 − 2 − k {displaystyle extstyle 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 ≡ ( a n ) ( mod n ) {displaystyle extstyle a^{(n-1)/2}equiv left({frac {a}{n}} ight){pmod {n}}} r = ( a n ) = ( 11 19 ) = 1 {displaystyle r=left({frac {a}{n}} ight)=left({frac {11}{19}} ight)=1} s = a ( n − 1 ) / 2 = 11 ( 19 − 1 ) / 2 ( mod 19 ) = 1 {displaystyle extstyle s=a^{(n-1)/2}=11^{(19-1)/2}{pmod {19}}=1} Получили, что r = s {displaystyle extstyle r=s} поэтому переходим к следующей итерации k = 2 Выберем случайное число a = 5; 2 < a < n - 1 Проверим условие НОД(a,n)>1 НОД(5,19)=1; значит проверяем выполнение сравнения a ( n − 1 ) / 2 ≡ ( a n ) ( mod n ) {displaystyle extstyle a^{(n-1)/2}equiv left({frac {a}{n}} ight){pmod {n}}} r = ( a n ) = ( 5 19 ) = 1 {displaystyle r=left({frac {a}{n}} ight)=left({frac {5}{19}} ight)=1} s = a ( n − 1 ) / 2 = 5 ( 19 − 1 ) / 2 ( mod 19 ) = 1 {displaystyle extstyle s=a^{(n-1)/2}=5^{(19-1)/2}{pmod {19}}=1} r = s {displaystyle extstyle r=s} и это была последняя итерация, отсюда делаем вывод, что 19 - простое число с вероятностью 1 − 2 − 2 {displaystyle 1-2^{-2}}

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

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

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

Применение

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

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

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