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

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

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

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

Натуральное n $(n\geq 2)$ называется псевдопростым по основанию a, где $~1<a<n$, если a и n взаимнопросты, и $a^{n-1} \equiv 1 (mod ~n)$.

Нечетное составное число m называется псевдопростым эйлеровым числом по основанию w, если оно удовлетворяет сравнению $~w^{(m-1)/2} \equiv \left( {w\over m} \right) (mod~ m)$, где $\left( {w\over m} \right)$ есть символ Лежандра.

Так как из сравнения $~w^{(m-1)/2} \equiv \left( {w\over m} \right) (mod~ m)$ следует, что $~w^{(m-1)} \equiv 1 (mod~ m)$ , то псевдопростое эйлерово число по основанию w так же является псевдопростым числом по основанию w.

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

Тест Соловея — Штрассена опирается на малую теорему Ферма и свойства символа Лежандра. Основан на следующем утверждении:

• Если m — нечетное составное число, то количество целых чисел w, взаимнопростых с m, удовлетворяющих сравнению $~w^{(m-1)/2} \equiv \left( {w\over m} \right) (mod~ m)$ и таких, что $1\leq w < m$, не превосходит $\frac {m}{2}$.

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

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

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

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

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

вывести, что m — вероятно простое, и остановиться.

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

На каждой итерации алгоритма составное число может быть распознано с вероятностью не менее 1 / 2. После k независимых итераций, эта вероятность составляет 2 ^{− k}.

Эта степень надежности теста Соловея — Штрассена иногда признается неудовлетворительной,^[2] так как, например, более новый тест Миллера — Рабина достигает вероятности ошибки не более 4 ^{- k} после k итераций алгоритма.

Алгоритм требует O(klog₂n) операций над длинными целыми числами.^[1]

Примечания

1. ↑ ^{1 2} Solovay, Robert M. and Volker Strassen (1977, submitted in 1974). «A fast Monte-Carlo test for primality». SIAM Journal on Computing 6 (1): 84–85. DOI:10.1137/0206006.
2. ↑ http://www.vntr.ru/ftpgetfile.php?id=323

Литература

1. Н. Коблиц. Курс теории чисел и криптографии. — ISBN 5-94057-103-4

Ссылки

1. http://www.ssl.stu.neva.ru/psw/crypto/open_key_crypt.pdf
2. http://gultyaeva.sdbe.ami.nstu.ru/fti&c/Materials/lr_fti&c.pdf