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

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

Концепции [ править ]

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

${\ Displaystyle а ^ {(р-1) / 2} \ эквив \ влево ({\ гидроразрыва {а} {р}} \ вправо) {\ pmod {р}}}$

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

Учитывая нечетное число n, мы можем подумать, действительно ли сравнение

${\ Displaystyle а ^ {(п-1) / 2} \ эквив \ влево ({\ гидроразрыва {а} {п}} \ вправо) {\ pmod {п}}}$

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

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

${\ Displaystyle а \ в (\ mathbb {Z} / п \ mathbb {Z}) ^ {*}}$

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

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

Пример [ править ]

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

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

• a ^{( n - 1) / 2 по} модулю n  = ^{47110 по} модулю 221 = -1 по модулю 221
• ${\ Displaystyle ({\ tfrac {а} {п}})}$по модулю n  = по  модулю 221 = −1 по модулю 221.${\ displaystyle ({\ tfrac {47} {221}})}$

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

• a ^{( n −1) / 2 по} модулю n  = ^{2110 по} модулю 221 = 30 по модулю 221
• ${\ Displaystyle ({\ tfrac {а} {п}})}$по модулю n  = по  модулю 221 = −1 по модулю 221.${\ displaystyle ({\ tfrac {2} {221}})}$

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

Алгоритм и время работы [ править ]

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

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

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

Точность теста [ править ]

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

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

${\displaystyle (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}}.}$

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

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

теперь мы знаем это

${\displaystyle (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 ^{- k} (сравните это с вероятностью отказа для теста простоты Миллера-Рабина , которая составляет не более 4 ^{- k} ).

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

Поведение в среднем случае [ править ]

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

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

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

Сложность [ править ]

Алгоритм Соловея – Штрассена показывает, что задача решения КОМПОЗИТ относится к классу сложности RP . ^[7]

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Соловей, Роберт М .; Штрассен, Фолькер (1977). «Быстрый тест Монте-Карло на простоту». SIAM Journal on Computing . 6 (1): 84–85. DOI : 10.1137 / 0206006 .См. Также Solovay, Robert M .; Штрассен, Фолькер (1978). «Опечатка: быстрый тест Монте-Карло на простоту». SIAM Journal on Computing . 7 (1): 118. DOI : 10,1137 / 0207009 .
• Дицфельбингер, Мартин (29.06.2004). «Проверка простоты за полиномиальное время, от рандомизированных алгоритмов до« ПРИМЕРЫ в P » ». Конспект лекций по информатике . 3000 . ISBN 978-3-540-40344-9.

Внешние ссылки [ править ]

• Соловея-Strassen Выполнение теста на простоту Соловея-Штрассен в Maple