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

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

История

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

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

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

Обоснование

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

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

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

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

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

 Необходимость следует из критерия Эйлера для символа Лежандра. 
 Для доказательства достаточности воспользуемся методом от противного.
 Предположим, что n — составное и при этом  для [math]\displaystyle{  \forall a \in\mathbf {Z_{n}}  }[/math]   выполнено сравнение  [math]\displaystyle{  a^{(n-1)/2} \equiv \left( \frac{a}{n}\right)\pmod {n} }[/math]
 [math]\displaystyle{  a^{n-1} = (a^{(n-1)/2})^{2}  = \left( \frac{a}{n}\right)^{2} }[/math]
 [math]\displaystyle{  \left( \frac{a}{n}\right)^{2} = 1   }[/math] Отсюда следует [math]\displaystyle{  a^{n-1} = 1 (mod n)   }[/math]
 Получаем, что  n— число Кармайкла, поэтому   [math]\displaystyle{  n =  p_{1}p_{2}..p_{k} }[/math]  где [math]\displaystyle{  p_{i} }[/math] - простое i = 1,2, ...k
 Рассмотрим b такое, что  [math]\displaystyle{  \left( \frac{b}{p_{1}}\right) = -1 (mod n)   }[/math] 
 Найдем такое  a , что :[math]\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}    }[/math]
 Такое а  существует по китайской теореме об остатках и принадлежит [math]\displaystyle{  Z_{n}  }[/math], так как является взаимно простым с n.
 [math]\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  }[/math]
[math]\displaystyle{  a^{(n-1)/2} \equiv \left( \frac{a}{n}\right)\pmod{n} }[/math]
[math]\displaystyle{   \left( \frac{a}{n}\right) = -1    }[/math]  Отсюда [math]\displaystyle{   a^{(n-1)/2} \equiv \ -1 (mod n)  }[/math]
[math]\displaystyle{   a^{(n-1)/2} \equiv \ -1 (mod p_{1})   }[/math]
[math]\displaystyle{   a^{(n-1)/2} \equiv \ -1 (mod p_{2})   }[/math]   противоречие с тем, что [math]\displaystyle{   a \equiv \ 1 (mod p_{i})   }[/math]
Значит неверно наше предположение о том, что  n -   составное.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Применение

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

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

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

См. также

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

Литература

1. Коблиц Н. Курс теории чисел и криптографии. — 2-ое. — М.: Научное издательство ТВП, 2001. — С. 149—160. — 254 с. — ISBN 5-94057-103-4.
2. Нестеренко А. Введение в современную криптографию.Теоретико-числовые алгоритмы. — 2011. — С. 79—90. — 190 с. — ISBN 978-5-94506-320-4.
3. Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии. — М.: МЦНМО, 2001. — С. 42—59. — 104 с. — ISBN 5-94057-060-7. Архивная копия от 31 мая 2013 на Wayback Machine
4. Саломаа А. Криптография с открытым ключом / Пер. с англ. И.А. Вихлянцева. — М.: Мир, 1995. — С. 176—184. — 318 с. — ISBN 5-03-001991-X. Архивная копия от 19 ноября 2011 на Wayback Machine