Тест Соловея — Штрассена — імовірнісний тест простоти, відкритий у 1970-х роках Робертом Мартіном Соловеем спільно з Фолькером Штрассеном. Тест завжди коректно визначає, що просте число є простим, але для складених чисел з деякою ймовірністю він може дати неправильну відповідь. Основна перевага тесту полягає в тому, що він, на відміну від тесту Ферма, розпізнає числа Кармайкла як складені.
Історія У 17 столітті Ферма довів твердження, назване пізніше малою теоремою Ферма, що слугує основою тесту Ферма на простоту: Якщо n — просте і a не ділиться на n, то . Ця перевірка для заданого n не вимагає великих обчислень, однак твердження, протилежне цьому, є невірним. Так, існують числа Кармайкла, які є складеними, для яких твердження, наведене в малій теоремі Ферма, виконується для всіх цілих чисел взаємнопростих з заданим числом. У 1994 році було показано, що таких чисел нескінченно багато. У зв'язку з виявленим недоліком тесту Ферма, актуальності набуло завдання збільшення достовірності ймовірнісних тестів. Першим тест, що відсіює числа Кармайкла як складені, запропонував Леманн. Цей недолік відсутній також у тестах Соловея — Штрассена і Міллера — Рабіна за рахунок більш сильного критерію відсіву, ніж мала теорема Ферма. Незалежно від один одного Д. Лемер в 1976 році і Р. Соловей спільно з Ф. Штрассеном в 1977 році довели, що аналога чисел Кармайкла, які є складеними і одночасно ейлеровими псевдопростими, немає. На основі цього і був запропонований тест Соловея — Штрассена на простоту, він був опублікований в 1977 році, доповнення до нього в 1978 році.
Обґрунтування Тест Соловея — Штрассена спирається на малу теорему Ферма і властивості символу Якобі: Якщо n — непарне складене число, то кількість цілих чисел a, взаємнопростих з n і менших n, що задовольняють порівнянню не перевищує . Складені числа n, що задовольняють цьому порівнянню називаються псевдопростими Ейлера-Якобі за основою a.
Алгоритм Соловея — Штрассена Алгоритм Соловея — Штрассена параметризується кількістю ітерацій k. У кожній ітерації випадковим чином вибирається число a < n. Якщо НСД(a,n) > 1, то виноситься рішення, що n - складене. Інакше перевіряється справедливість порівняння . Якщо воно не виконується, то виноситься рішення, що n — складене. Якщо це порівняння виконується, то a є свідком простоти числа n. Далі вибирається інше випадкове a і процедура повторюється. Після знаходження k свідків простоти в k ітераціях виноситься висновок, що n є простим числом з імовірністю .
На псевдокоді алгоритм може бути записаний наступним чином: Ввід: > 2, непарне натуральне число, що тестується; , параметр, що визначає точність тесту. Вивід: складене, означає, що точно складене; ймовірно просте, означає, що ймовірно є простим.
for i = 1, 2, ..., : = випадкове ціле від 2 до , включно; якщо НСД(a, n) > 1, тоді: вивести, що — складене, і зупинитися. якщо , тоді: вивести, що — складене, і зупинитися.
інакше вивести, що — просте зі ймовірністю , і зупинитися.
Приклад застосування алгоритму Перевіримо число n = 19 на простоту. Виберемо параметр точності k = 2. k = 1 Виберемо довільне число a = 11; 2 < a < n - 1 Перевіримо умову НСД(a,n)>1 НСД(11,19)=1; отже, перевіряємо виконання порівняння
Отримали, що , тому переходимо до наступної ітерації
k = 2 Виберемо довільне число a = 5; 2 < a < n - 1 Перевіримо умову НСД(a,n)>1 НСД(5,19)=1; отже, перевіряємо виконання порівняння
і це була остання ітерація, звідси робимо висновок, що 19 - просте число з імовірністю
Обчислювальна складність і точність Точність у порівнянні з іншими ймовірнісними тестами на простоту (тут k — число незалежних ітерацій) назва тестуймовірність (що число складене)Б. Шнайер Прикладная криптография — М. : ТРИУМФ, 2002 . — Глава 11.приміткиФермане розпізнає числа Кармайкла як складеніЛеманнаСоловея — Штрассена Теоретична складність обчислень всіх наведених у таблиці тестів оцінюється як . Алгоритм вимагає операцій над довгими цілими числами. При реалізації алгоритму, для зниження обчислювальної складності, числа a вибираються з інтервалу 0 < a < c < n, де c — константа рівна максимально можливому значенню натурального числа, що міститься в одному регістрі процесора.
Застосування Ймовірнісні тести застосовуються в системах заснованих на проблемі факторизації, наприклад RSA або схема Рабіна. Однак на практиці ступінь достовірності тесту Соловея — Штрассена не є достатньою, замість нього використовується тест Міллера — Рабіна. Більш того, використовуються об'єднані алгоритми, наприклад пробний поділ і тест Міллера — Рабіна, при правильному виборі параметрів можна отримати кращі результати, ніж при застосуванні кожного тесту окремо.
Поліпшення тесту У 2005 році на Міжнародній конференції Bit+ «Informational Technologies -2005» А. А. Балабанов, А. Ф. Агафонов, В. А. Рику запропонували модернізований тест Соловея — Штрассена. Тест Соловея — Штрассена заснований на обчисленні символу Якобі, що займає час, еквівалентний . Ідея поліпшення полягає в тому, щоб у відповідності з теоремою квадратичного закону взаємності Гаусса, перейти до обчислення величини ,що є оберненою символу Якобі, що є більш простою процедурою.Балабанов А. А.,Агафонов А. Ф.,Рыку В. А.Алгоритм быстрой генерации ключей в криптографической системе RSA. — Вестник научно-технического развития, 2009 № 7(23). — С. 11..
Див. також Псевдопросте число
Примітки
Література