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

Тест на простоту Соловея–Штрассена , разработанный Робертом М. Соловеем и Фолькером Штрассеном в 1977 году, является вероятностным тестом для определения того, является ли число составным или, вероятно, простым . Идея теста была открыта М. М. Артюховым в 1967 году ^[1] (см. теорему E в статье). Этот тест был в значительной степени вытеснен тестом на простоту Бейли–ПСВ и тестом на простоту Миллера–Рабина , но имеет большое историческое значение, показывая практическую осуществимость криптосистемы RSA . Тест Соловея–Штрассена по сути является тестом Эйлера–Якоби на вероятное простое число .

Концепции

Эйлер доказал ^[2] , что для любого нечетного простого числа p и любого целого числа a ,

a^{(p-1)/2}\equiv \left({\frac {a}{p}}\right){\pmod {p}}

где — символ Лежандра . Символ Якоби является обобщением символа Лежандра до , где n может быть любым нечетным целым числом. Символ Якоби может быть вычислен за время O ((log n )²) с использованием обобщения Якоби закона квадратичной взаимности . $\left({\tfrac {a}{p}}\right)$ $\left({\tfrac {a}{n}}\right)$

При наличии нечетного числа n можно поразмыслить, выполняется ли сравнение

a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}

справедливо для различных значений «основания» a , при условии, что a взаимно просто с n . Если n простое, то это сравнение верно для всех a . Поэтому, если мы выберем значения a случайным образом и проверим сравнение, то как только мы найдем a, которое не соответствует сравнению, мы узнаем, что n не является простым (но это не говорит нам о нетривиальной факторизации n ). Это основание a называется свидетелем Эйлера для n ; это свидетель составности n . Основание a называется лжецом Эйлера для n , если сравнение верно, а n составное.

Для каждого составного нечетного n , по крайней мере, половина всех оснований

a\in (\mathbb {Z} /n\mathbb {Z} )^{*}

являются (эйлеровыми) свидетелями, поскольку множество лжецов Эйлера является собственной подгруппой . Например, для множество лжецов Эйлера имеет порядок 8 и , а также имеет порядок 48. $(\mathbb {Z} /n\mathbb {Z})^{*}$ $n=65$ $=\{1,8,14,18,47,51,57,64\}$ $(\mathbb {Z} /n\mathbb {Z})^{*}$

Это контрастирует с тестом Ферма на простоту , для которого доля свидетелей может быть намного меньше. Таким образом, не существует (нечетных) составных n без многих свидетелей, в отличие от случая чисел Кармайкла для теста Ферма.

Пример

Предположим, мы хотим определить, является ли n = 221 простым числом. Запишем ( n −1)/2=110.

Мы случайным образом выбираем a (больше 1 и меньше n ): 47. Используя эффективный метод возведения числа в степень (mod n ), такой как двоичное возведение в степень , мы вычисляем:

a ^{( n −1)/2} mod n = 47 ¹¹⁰ mod 221 = −1 mod 221
$({\tfrac {a}{n}})$ mod n = mod 221 = −1 mod 221. $({\tfrac {47}{221}})$

Это дает нам следующее: либо 221 — простое число, либо 47 — эйлеров лжец для 221. Мы пробуем еще одно случайное число a , на этот раз выбирая a = 2:

a ^{( n −1)/2} mod n = 2 ¹¹⁰ mod 221 = 30 mod 221
$({\tfrac {a}{n}})$ mod n = mod 221 = −1 mod 221. $({\tfrac {2}{221}})$

Следовательно, 2 является свидетелем Эйлера для составности 221, а 47 на самом деле был лжецом Эйлера. Обратите внимание, что это ничего не говорит нам о простых множителях 221, которые на самом деле являются 13 и 17.

Алгоритм и время выполнения

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

входные данные : n , значение для проверки на простоту k , параметр, определяющий точность теста выходные данные : составное число , если n является составным числом, в противном случае, вероятно, простое числоповторить  k раз: выбрать a случайным образом в диапазоне [2, n − 1] если  $x$  $= 0$ или тогда вернуть составное число вернуть вероятно простое число $x\gets \left({\tfrac {a}{n}}\right)$      $a^{(n-1)/2}\not \equiv x{\pmod {n}}$

При использовании быстрых алгоритмов модульного возведения в степень время работы этого алгоритма составляет O( k ·log ³ n ), где k — количество различных значений a , которые мы проверяем.

Точность теста

Алгоритм может вернуть неверный ответ. Если входное число n действительно является простым, то выходное число всегда будет верно вероятно простым . Однако если входное число n является составным, то выходное число может быть неверно вероятно простым . Тогда число n называется псевдопростым числом Эйлера–Якоби .

Когда n нечетное и составное, по крайней мере половина всех a с gcd( a , n ) = 1 являются свидетелями Эйлера. Мы можем доказать это следующим образом: пусть { a ₁ , a ₂ , ..., a _m } будут лжецами Эйлера, а a — свидетелем Эйлера. Тогда для i = 1,2,..., m :

(a\cdot a_{i})^{(n-1)/2}=a^{(n-1)/2}\cdot a_{i}^{(n-1)/2}=a^{(n-1)/2}\cdot \left({\frac {a_{i}}{n}}\right)\not \equiv \left({\frac {a}{n}}\right)\left({\frac {a_{i}}{n}}\right){\pmod {n}}.

Потому что справедливо следующее:

\left({\frac {a}{n}}\right)\left({\frac {a_{i}}{n}}\right)=\left({\frac {a\cdot a_{i}}{n}}\right),

теперь мы знаем, что

(a\cdot a_{i})^{(n-1)/2}\not \equiv \left({\frac {a\cdot a_{i}}{n}}\right){\pmod {n}}.

Это дает, что каждый a _i дает число a · a _i , которое также является свидетелем Эйлера. Таким образом, каждый лжец Эйлера дает свидетеля Эйлера, и поэтому число свидетелей Эйлера больше или равно числу лжецов Эйлера. Следовательно, когда n является составным, по крайней мере половина всех a с gcd( a , n ) = 1 является свидетелем Эйлера.

Следовательно, вероятность неудачи не превышает 2 ^{− k} (сравните это с вероятностью неудачи для теста простоты Миллера–Рабина , которая не превышает 4 ^{− k} ).

Для целей криптографии , чем больше баз a мы проверяем, т. е. если мы выбираем достаточно большое значение k , тем выше точность проверки. Следовательно, вероятность того, что алгоритм потерпит неудачу таким образом, настолько мала, что (псевдо)простое число используется на практике в криптографических приложениях, но для приложений, для которых важно иметь простое число, следует использовать тест типа ECPP или тест простоты Поклингтона ^{[3], который}доказывает простоту.

Среднестатистическое поведение

Граница 1/2 вероятности ошибки одного раунда теста Соловея-Штрассена сохраняется для любого входного значения n , но те числа n , для которых граница (приблизительно) достигается, встречаются крайне редко. В среднем вероятность ошибки алгоритма значительно меньше: она меньше, чем

2^{-k}\exp \left(-(1+o(1)){\frac {\log x\,\log \log \log x}{\log \log x}}\right)

для k раундов теста, примененного к равномерно случайному числу n ≤ x . ^[4]^[5] Та же граница применима и к связанной задаче о том, какова условная вероятность того, что n является составным числом для случайного числа n ≤ x , которое было объявлено простым в k раундах теста.

Сложность

Алгоритм Соловея–Штрассена показывает, что задача принятия решения COMPOSITE относится к классу сложности RP . ^[6]

Ссылки

^ Артюхов, ММ (1966–1967), «Некоторые критерии простоты чисел, связанные с малой теоремой Ферма», Acta Arithmetica , 12 : 355–364, MR 0213289
^ Критерий Эйлера
^ Тест Поклингтона на Mathworld
^ П. Эрдёш; К. Померанс (1986). «О числе ложных свидетелей для составного числа». Математика вычислений . 46 (173): 259–279. doi :10.2307/2008231. JSTOR 2008231.
^ I. Damgård; P. Landrock; C. Pomerance (1993). "Оценки средней ошибки для сильного вероятного простого теста". Mathematics of Computation . 61 (203): 177–194. doi :10.2307/2152945. JSTOR 2152945.
^ Р. Мотвани; П. Рагхаван (1995). Рандомизированные алгоритмы . Cambridge University Press. С. 417–423. ISBN 978-0-521-47465-8.

Дальнейшее чтение

Соловей, Роберт М.; Штрассен, Фолькер (1977). «Быстрый тест Монте-Карло на простоту». Журнал SIAM по вычислениям . 6 (1): 84–85. doi :10.1137/0206006.См. также Solovay, Robert M.; Strassen, Volker (1978). "Erratum: A fast Monte-Carlo test for primality". SIAM Journal on Computing . 7 (1): 118. doi :10.1137/0207009.
Дицфельбингер, Мартин (29.06.2004). «Проверка простоты за полиномиальное время: от рандомизированных алгоритмов до «PRIMES is in P»". Конспект лекций по информатике . Том 3000. Springer. ISBN 978-3-540-40344-9.

Внешние ссылки

Реализация теста Соловея-Штрассена на простоту в Maple