Тест Соловея — Штрассена — вероятностный тест простоты, открытый в 1970-х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном.[1] Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью он может дать неверный ответ. Основное преимущество теста заключается в том, что он, в отличие от теста Ферма, распознает числа Кармайкла как составные.
В 17 веке Ферма доказал утверждение, названное позже малой теоремой Ферма, служащее основой теста Ферма на простоту:
Эта проверка для заданного n не требует больших вычислений, однако утверждение, обратное этому, неверно. Так, существуют числа Кармайкла, являющиеся составными, для которых утверждение, приведенное в малой теореме Ферма, выполняется для всех целых чисел взаимнопростых с заданным числом. В 1994 году было показано, что таких чисел бесконечно много.[2] В связи с обнаруженным недостатком теста Ферма, актуальность приобрела задача увеличения достоверности вероятностных тестов. Первым тест, отсеивающий числа Кармайкла как составные, предложил Леманн. Этот недостаток отсутствует также в тестах Соловея — Штрассена и Миллера — Рабина за счет более сильного критерия отсева, чем малая теорема Ферма. Независимо от друг друга Д. Лемер в 1976 году и Р. Соловей совместно с Ф. Штрассеном в 1977 году доказали, что аналога чисел Кармайкла, которые являются составными и одновременно эйлеровыми псевдопростыми, нет.[3] На основе этого и был предложен тест Соловея — Штрассена на простоту, он был опубликован в 1977 году, дополнения к нему в 1978 году.
Тест Соловея — Штрассена опирается на малую теорему Ферма и свойства символа Якоби [4]:
Составные числа n удовлетворяющие этому сравнению называются псевдопростыми Эйлера-Якоби по основанию a.
Необходимость следует из критерия Эйлера для символа Лежандра. Для доказательства достаточности воспользуемся методом от противного. Предположим, что n — составное и при этом для выполнено сравнение Отсюда следует Получаем, что n— число Кармайкла, поэтому где - простое i = 1,2, ...k Рассмотрим b такое, что Найдем такое a , что : Такое а существует по китайской теореме об остатках и принадлежит , так как является взаимно простым с n. Отсюда противоречие с тем, что Значит неверно наше предположение о том, что n - составное.
Алгоритм Соловея — Штрассена [6] параметризуется количеством раундов 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 - простое число с вероятностью
название теста | вероятность(что число составное)[7] | примечания |
---|---|---|
Ферма | не распознает числа Кармайкла как составные | |
Леманна | ||
Соловея — Штрассена |
Вероятностные тесты применяются в системах основанных на проблеме факторизации, например RSA или схема Рабина. Однако на практике степень достоверности теста Соловея — Штрассена не является достаточной, вместо него используется тест Миллера — Рабина. Более того, используются объединенные алгоритмы, например пробное деление и тест Миллера — Рабина, при правильном выборе параметров можно получить результаты лучше, чем при применении каждого теста по отдельности.[7]
В 2005 году на Международной конференции Bit+ «Informational Technologies −2005» А. А. Балабанов, А. Ф. Агафонов, В. А. Рыку предложили модернизированный тест Соловея — Штрассена. Тест Соловея — Штрассена основан на вычислении символа Якоби, что занимает время эквивалентное . Идея улучшения состоит в том, чтобы в соответствии с теоремой квадратичной взаимности Гаусса, перейти к вычислению величины ,являющейся обратной символу Якоби, что является более простой процедурой.[8].
|year=
(справка на английском)Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .