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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

История[править | править вики-текст]

В 17 веке Ферма доказал утверждение, названное позже малой теоремой Ферма, служащее основой теста Ферма на простоту: Если n - простое и a не делится на n, то a^{n-1} \equiv 1\pmod{n}. Эта проверка для заданного n не требует больших вычислений, однако утверждение обратное этому, неверно. Кроме того, существуют числа Кармайкла, являющиеся составными, для которых утверждение, приведенное в малой теореме Ферма, выполняется для всех целых чисел взаимнопростых с заданным числом. В 1994 году было показано, что таких чисел бесконечно много. [2] В связи с обнаруженным недостатком теста Ферма, актуальность приобрела задача увеличения достоверности вероятностных тестов. Первым тест, отсеивающий числа Кармайкла как составные, предложил Леманн. Этот недостаток отсутствует также в тестах Соловея-Штрассена и Миллера-Рабина за счет более сильного критерия отсева, чем малая теорема Ферма. Независимо от друг друга Д. Лемер в 1976 году и Р. Соловей совместно с Ф. Штрассеном в 1977 году доказали, что аналога чисел Кармайкла, которые являются составными и одновременно эйлеровыми псевдопростыми, нет.[3] На основе этого и был предложен тест Соловея-Штрассена на простоту, он был опубликован в 1977 году, дополнения к нему в 1978 году.

Обоснование[править | править вики-текст]

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

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

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

Алгоритм Соловея — Штрассена[править | править вики-текст]

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

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

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

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

вывести, что n простое  с вероятностью \textstyle 1 - 2^{-k} , и остановиться.

Пример применения алгоритма[править | править вики-текст]

Проверим число n = 19 на простоту.Выберем параметр точности k = 2.

 k = 1
 Выберем случайное число a = 11;  2 < a < n - 1
 Проверим условие НОД(a,n)>1
 НОД(11,19)=1; значит проверяем выполнение сравнения  \textstyle a^{(n-1)/2} \equiv \left( \frac{a}{n} \right)\pmod{n}  
  r = \left( \frac{a}{n} \right) = \left( \frac{11}{19} \right) = 1 
 \textstyle s = a^{(n-1)/2} =   11^{(19-1)/2}\pmod{19} = 1 
 Получили, что \textstyle r = s   поэтому переходим к следующей итерации
 k = 2
 Выберем случайное число a = 5;    2 < a < n - 1
 Проверим условие НОД(a,n)>1
 НОД(5,19)=1;  значит проверяем выполнение сравнения  \textstyle a^{(n-1)/2} \equiv \left( \frac{a}{n} \right)\pmod{n}  
  r = \left( \frac{a}{n} \right) = \left( \frac{5}{19} \right) = 1 
 \textstyle s = a^{(n-1)/2} = 5^{(19-1)/2}\pmod{19} = 1 
 \textstyle r = s    и это была последняя итерация, отсюда делаем вывод, что 19 - простое число с вероятностью  1 - 2^{-2} 

Вычислительная сложность и точность[править | править вики-текст]

  • Точность по сравнению с другими вероятностными тестами на простоту

( k - число независимых раундов )


название теста вероятность(что число составное) [7] примечания
Ферма   2^{-k} не распознает числа Кармайкла как составные
Леманна  2^{-k}
Соловея-Штрассена  2^{-k}


  • Теоретическая сложность вычислений всех приведенных в таблице тестов оценивается как O(\log^3n) .[3]
  • Алгоритм требует O(k \log_2 m) операций над длинными целыми числами.[1]
  • При реализации алгоритма, для снижения вычислительной сложности, числа a выбираются из интервала 0 < a < c < n, где c - константа равная максимально возможному значению натурального числа, помещающегося в одном регистре процессора.[6]

Применение[править | править вики-текст]

Вероятностные тесты применяются в системах основанных на проблеме факторизации, например RSA или схема Рабина. Однако на практике степень достоверности теста Соловея-Штрассена не является достаточной, вместо него используется тест Миллера-Рабина. Более того, используются объединенные алгоритмы, например пробное деление и тест Миллера-Рабина, при правильном выборе параметров можно получить результаты лучше, чем при применении каждого теста по отдельности. [7]

Улучшение теста[править | править вики-текст]

В 2005 году на Международной конференции Bit+ “Informational Technologies -2005” А.А. Балабанов, А.Ф. Агафонов, В.А. Рыку предложили модернизированный тест Соловея-Штрассена. Тест Соловея-Штрассена основан на вычислении символа Якоби, что занимает время эквивалентное   \log_{2} n . Идея улучшения состоит в том, чтобы в соответствии с теоремой квадратичной взаимности Гаусса, перейти к вычислению величины  \left( \frac{n}{a}\right) ,являющейся обратной символу Якоби, что является более простой процедурой. [8].

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  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. W. R. Alford, A. Granville, C. Pomerance (1994). «There are Infinitely Many Carmichael Numbers». Annals of Mathematics 139: 703-722. DOI:10.2307/2118576.
  3. 1 2 Черемушкин, 2001
  4. 1 2 Нестеренко, 2011
  5. Н.Ю. Золотых. Лекции по компьютерной алгебре. Лекция 6. Теорема Кармайкла.Тест Соловея-Штрассена.
  6. 1 2 Нестеренко, 2011
  7. 1 2 Б. Шнайер Прикладная криптография — М. : ТРИУМФ, 2002 . — Глава 11.
  8. Балабанов А.А.,Агафонов А.Ф.,Рыку В.А.Алгоритм быстрой генерации ключей в криптографической системе RSA. — Вестник научно-технического развития, 2009 №7(23). — С. 11.

Литература[править | править вики-текст]

  1. Коблиц Н. Курс теории чисел и криптографии. — 2-ое. — М.: Научное издательство ТВП, 2001. — С. 149 - 160. — 254 с. — ISBN 5-94057-103-4
  2. Нестеренко А. Введение в современную криптографию.Теоретико-числовые алгоритмы. — 2011. — С. 79 - 90. — 190 с. — ISBN 978-5-94506-320-4
  3. Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии. — М.: МЦНМО, 2001. — С. 42 - 59. — 104 с. — ISBN 5-94057-060-7
  4. Саломаа А. Криптография с открытым ключом / Пер. с англ. И.А. Вихлянцева. — М.: Мир, 1995. — С. 176 - 184. — 318 с. — ISBN 5-03-001991-X

Ссылки[править | править вики-текст]

  1. http://gultyaeva.sdbe.ami.nstu.ru/fti&c/Materials/lr_fti&c.pdf