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

Обоснование

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

• Если m — нечетное составное число, то количество целых чисел w, взаимнопростых с m и меньших m, удовлетворяющих сравнению , не превосходит .

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

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

Алгоритм Соловея — Штрассена параметризуется количеством раундов k. В каждом раунде случайным образом выбирается число w < m. Если НОД(w,m) > 1, то выносится решение, что m составное. Иначе проверяется справедливость сравнения . Если оно не выполняется, то выносится решение, что m - составное. Если это сравнение выполняется, то w является свидетелем простоты числа m. Далее выбирается другое случайное w и процедура повторяется. После нахождения k свидетелей простоты в k раундах выносится заключение, что m вероятно является простым числом. Нетрудно видеть, что для проверки этого сравнения достаточно вычислять по модулю m (англ.).

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

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

for i = 1, 2, ..., :
    = случайное целое от 2 до , включительно;
   если НОД(w, m) > 1, тогда:
       вывести, что  — составное, и остановиться.
   если , тогда: 
       вывести, что  — составное, и остановиться.

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

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

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

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

См. также

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

Примечания

Литература

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