Solovay–Strassen primality test

Тест Соловея-Штрассена на простоту , разработанный Робертом М. Соловеем и Фолькером Штрассеном в 1977 году, представляет собой вероятностный тест, позволяющий определить, является ли число составным или, вероятно, простым . Идею теста открыл М.М. Артюхов в 1967 году. (см. теорему E в статье). Этот тест был в значительной степени заменен тестом на простоту Бэйли-PSW и тестом простоты Миллера-Рабина , но он имеет большое историческое значение для демонстрации практической осуществимости RSA криптосистемы . Критерий Соловея-Штрассена по сути представляет собой тест Эйлера-Якоби на вероятность простых чисел .

Концепции

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

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

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

Учитывая нечетное число 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} )^{*}$

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

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

Пример

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

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

• а ^{( п -1)/2} против n = 47 ¹¹⁰ мод 221 = −1 мод 221
• $({\tfrac {a}{n}})$ против n = $({\tfrac {47}{221}})$ мод 221 = −1 мод 221.

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

• а ^{( п -1)/2} против n = 2 ¹¹⁰ мод 221 = 30 мод 221
• $({\tfrac {a}{n}})$ против n = $({\tfrac {2}{221}})$ мод 221 = −1 мод 221.

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

Алгоритм и время работы

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

inputs: n, a value to test for primality
        k, a parameter that determines the accuracy of the test
output: composite if n is composite, otherwise probably prime

repeat k times:
    choose a randomly in the range [2,n − 1]
    $x\gets \left({\tfrac {a}{n}}\right)$
    if x = 0 or $a^{(n-1)/2}\not \equiv x{\pmod {n}}$ then 
        return composite
return probably prime

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

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

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

Когда n нечетное и составное, по крайней мере половина всех a с НОД( 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 с НОД( a , n ) = 1 является свидетелем Эйлера.

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

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

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

Граница 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 . Та же оценка применима и к связанной с ней проблеме: какова условная вероятность того, что n является составным для случайного числа n ≤ x , которое было объявлено простым в k раундах теста.

Сложность

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

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

• Соловей, Роберт М.; Штрассен, Волкер (1977). «Быстрый тест Монте-Карло на простоту». SIAM Journal по вычислительной технике . 6 (1): 84–85. дои : 10.1137/0206006 . См. также Соловей, Роберт М.; Штрассен, Волкер (1978). «Ошибка: быстрый тест Монте-Карло на простоту». SIAM Journal по вычислительной технике . 7 (1): 118. дои : 10.1137/0207009 .
• Дитцфельбингер, Мартин (29 июня 2004 г.). «Тестирование простоты за полиномиальное время, от рандомизированных алгоритмов до «ПРАЙМСЫ находятся в P» ». Конспекты лекций по информатике . Том. 3000. Спрингер. ISBN  978-3-540-40344-9 .

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

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