Тест Соловея — Штрассена (Myvm Vklkfyx — Omjgvvyug)

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

История

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

Если n — простое и a не делится на n, то

a^{n-1}\equiv 1{\pmod {n}}

.

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

Обоснование

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Применение

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

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

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

См. также

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

Примечания

↑ ¹ ² Solovay, Robert M. and Volker Strassen. A fast Monte-Carlo test for primality (англ.) // SIAM Journal on Computing^[англ.] : journal. — 1977, submitted in 1974. — Vol. 6, no. 1. — P. 84—85. — doi:10.1137/0206006.
↑ W. R. Alford, A. Granville, C. Pomerance. There are Infinitely Many Carmichael Numbers (англ.) // Annals of Mathematics : journal. — 1994. — Vol. 139. — P. 703—722. — doi:10.2307/2118576. Архивировано 4 мая 2012 года.
↑ ¹ ² Черемушкин, 2001, с. 48.
↑ ¹ ² Нестеренко, 2011, с. 82.
↑ Н.Ю. Золотых. Лекции по компьютерной алгебре. Лекция 6. Теорема Кармайкла.Тест Соловея - Штрассена. Архивная копия от 4 ноября 2014 на Wayback Machine
↑ ¹ ² Нестеренко, 2011, с. 84.
↑ ¹ ² Б. Шнайер Прикладная криптография — М. : ТРИУМФ, 2002 . — Глава 11.
↑ Балабанов А. А.,Агафонов А. Ф.,Рыку В. А.Алгоритм быстрой генерации ключей в криптографической системе RSA. Архивная копия от 5 ноября 2014 на Wayback Machine — Вестник научно-технического развития, 2009 № 7(23). — С. 11.

Литература

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

[sspaper-1] ¹ ² Solovay, Robert M. and Volker Strassen. A fast Monte-Carlo test for primality (англ.) // SIAM Journal on Computing^[англ.] : journal. — 1977, submitted in 1974. — Vol. 6, no. 1. — P. 84—85. — doi:10.1137/0206006.

[2] W. R. Alford, A. Granville, C. Pomerance. There are Infinitely Many Carmichael Numbers (англ.) // Annals of Mathematics : journal. — 1994. — Vol. 139. — P. 703—722. — doi:10.2307/2118576. Архивировано 4 мая 2012 года.

[_1bd60883afb25c9e-3] ¹ ² Черемушкин, 2001, с. 48.

[_a77e2bf863ab5d64-4] ¹ ² Нестеренко, 2011, с. 82.

[5] Н.Ю. Золотых. Лекции по компьютерной алгебре. Лекция 6. Теорема Кармайкла.Тест Соловея - Штрассена. Архивная копия от 4 ноября 2014 на Wayback Machine

[_a77e2bf863ab5d62-6] ¹ ² Нестеренко, 2011, с. 84.

[шнайер-7] ¹ ² Б. Шнайер Прикладная криптография — М. : ТРИУМФ, 2002 . — Глава 11.

[8] Балабанов А. А.,Агафонов А. Ф.,Рыку В. А.Алгоритм быстрой генерации ключей в криптографической системе RSA. Архивная копия от 5 ноября 2014 на Wayback Machine — Вестник научно-технического развития, 2009 № 7(23). — С. 11.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Теоретико-числовые алгоритмы
Тесты простоты	Миллера Миллера — Рабина Люка — Лемера Пепина Агравала — Каяла — Саксены Соловея — Штрассена
Поиск простых чисел	Перебор делителей Решето Эратосфена Решето Аткина Решето Сундарама
Факторизация	Перебор делителей Метод Ферма p−1-метод Полларда ρ-алгоритм Полларда Метод Лемана Метод эллиптических кривых (алгоритм Ленстры) Алгоритм Диксона Квадратичное решето
Дискретное логарифмирование	Алгоритм Гельфонда — Шенкса Алгоритм Полига — Хеллмана ρ-метод Полларда Алгоритм «кенгуру» Полларда Алгоритм Адлемана Алгоритм COS
Нахождение НОД	Алгоритм Евклида Расширенный алгоритм Бинарный алгоритм
Арифметика по модулю	Алгоритм Монтгомери Китайская теорема об остатках
Умножение и деление чисел	Алгоритм Карацубы Алгоритм Тоома — Кука Алгоритм Шёнхаге — Штрассена Алгоритм Фюрера Алгоритм Харви — ван дер Хувена Алгоритм Бурникеля — Циглера
Вычисление квадратного корня	Алгоритм Тонелли — Шенкса Алгоритм Берлекэмпа — Рабина