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

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

Обоснование

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

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

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

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

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

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

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

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

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

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

На каждом раунде алгоритма составное число может быть распознано с вероятностью не менее ½. После k независимых раундов, эта вероятность составляет $2^{-k}$, что хуже теста Миллера — Рабина имеющего вероятность ошибки не более $4^{-k}$.

Алгоритм требует $O(k\log _{2}m)$ операций над длинными целыми числами.

См. также

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

Литература

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