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

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

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

Тест Соловея — Штрассена — вероятностный тест простоты, открытый в 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(klog2n) операций над длинными целыми числами.[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



Wikimedia Foundation. 2010.

Смотреть что такое "Тест Соловея — Штрассена" в других словарях:

  • Тест Соловея — Штрассена вероятностный тест простоты, открытый в 1970 х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном.[1] Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью… …   Википедия

  • Тест простоты — Тест простоты  алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты. Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только… …   Википедия

  • Тест Ферма — Тест простоты Ферма в теории чисел  это тест простоты натурального числа n, основанный на малой теореме Ферма. Содержание Если n  простое число, то оно удовлетворяет сравнению для любого a, где n не делит a. Выполнение сравнения… …   Википедия

  • Тест Миллера (теория чисел) — У этого термина существуют и другие значения, см. Тест Миллера. Не следует путать с «Тестом Миллера Рабина»  вероятностным полиномиальным тестом простоты. Тест Миллера  детерминированный полиномиальный тест простоты. В 1976 году Миллер… …   Википедия

  • Тест простоты Люка — В теории чисел тест простоты Люка это тест простоты натурального числа n; для его работы необходимо знать разложение на множители. Для простого числа n простые множители числа вместе с некоторым основанием a составляют сертификат Пратта, который… …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

  • Критерий Поклингтона — детерминированный тест на простоту. Критерий Поклингтона позволяет определять, является ли простым данное число. Содержание 1 Теорема Поклингтона 2 Доказательство теоремы Поклингто …   Википедия

  • Псевдопростое число — Натуральное число называется псевдопростым, если оно обладает некоторыми свойствами простых чисел, являясь тем не менее составным числом. В зависимости от рассматриваемых свойств существует несколько различных типов псевдопростых чисел.… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»