Русская Википедия:Тест Соловея — Штрассена
Тест Соловея — Штрассена — вероятностный тест простоты, открытый в 1970-х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном.[1] Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью он может дать неверный ответ. Основное преимущество теста заключается в том, что он, в отличие от теста Ферма, распознает числа Кармайкла как составные.
История
В 17 веке Ферма доказал утверждение, названное позже малой теоремой Ферма, служащее основой теста Ферма на простоту:
- Если n — простое и a не делится на n, то <math>a^{n-1} \equiv 1\pmod{n}</math>.
Эта проверка для заданного n не требует больших вычислений, однако утверждение, обратное этому, неверно. Так, существуют числа Кармайкла, являющиеся составными, для которых утверждение, приведенное в малой теореме Ферма, выполняется для всех целых чисел взаимнопростых с заданным числом. В 1994 году было показано, что таких чисел бесконечно много.[2] В связи с обнаруженным недостатком теста Ферма, актуальность приобрела задача увеличения достоверности вероятностных тестов. Первым тест, отсеивающий числа Кармайкла как составные, предложил Леманн. Этот недостаток отсутствует также в тестах Соловея — Штрассена и Миллера — Рабина за счет более сильного критерия отсева, чем малая теорема Ферма. Независимо от друг друга Д. Лемер в 1976 году и Р. Соловей совместно с Ф. Штрассеном в 1977 году доказали, что аналога чисел Кармайкла, которые являются составными и одновременно эйлеровыми псевдопростыми, нет.Шаблон:Sfn На основе этого и был предложен тест Соловея — Штрассена на простоту, он был опубликован в 1977 году, дополнения к нему в 1978 году.
Обоснование
Тест Соловея — Штрассена опирается на малую теорему Ферма и свойства символа Якоби Шаблон:Sfn:
- Если n — нечетное составное число, то количество целых чисел a, взаимнопростых с n и меньших n, удовлетворяющих сравнению <math>\textstyle a^{(n-1)/2} \equiv \left( \frac{a}{n} \right)\pmod{n}</math>, не превосходит <math>\frac{n}{2}</math>.
Составные числа n удовлетворяющие этому сравнению называются псевдопростыми Эйлера-Якоби по основанию a.
Шаблон:Hider </math> выполнено сравнение <math> a^{(n-1)/2} \equiv \left( \frac{a}{n}\right)\pmod {n}</math>
<math> a^{n-1} = (a^{(n-1)/2})^{2} = \left( \frac{a}{n}\right)^{2}</math>
<math> \left( \frac{a}{n}\right)^{2} = 1 </math> Отсюда следует <math> a^{n-1} = 1 (mod n) </math>
Получаем, что n— число Кармайкла, поэтому <math> n = p_{1}p_{2}..p_{k}</math> где <math> p_{i}</math> - простое i = 1,2, ...k
Рассмотрим b такое, что <math> \left( \frac{b}{p_{1}}\right) = -1 (mod n) </math>
Найдем такое a , что :<math> a = \begin{cases}
b (mod {p_{1}}), & \mbox{if } i \mbox{= 1} \\
1 (mod {p_{i}}), & \mbox{if } i \mbox{ = 2,...,k}
\end{cases} </math>
Такое а существует по китайской теореме об остатках и принадлежит <math> Z_{n} </math>, так как является взаимно простым с n.
<math> \left( \frac{a}{n}\right) = \left( \frac{a}{p_{1}}\right) \left( \frac{a}{p_{2}}\right)....\left( \frac{a}{p_{k}}\right) = \left( \frac{a}{p_{1}}\right) = \left( \frac{b}{p_{1}}\right) = -1 </math>
<math> a^{(n-1)/2} \equiv \left( \frac{a}{n}\right)\pmod{n}</math>
<math> \left( \frac{a}{n}\right) = -1 </math> Отсюда <math> a^{(n-1)/2} \equiv \ -1 (mod n) </math>
<math> a^{(n-1)/2} \equiv \ -1 (mod p_{1}) </math>
<math> a^{(n-1)/2} \equiv \ -1 (mod p_{2}) </math> противоречие с тем, что <math> a \equiv \ 1 (mod p_{i}) </math>
Значит неверно наше предположение о том, что n - составное.
- Доказательство того, что количество таких чисел не превосходит n/2 можно найти в любом пособии по теоретико-числовым алгоритмам.Шаблон:Sfn
}}
Алгоритм Соловея — Штрассена
Алгоритм Соловея — Штрассена Шаблон:Sfn параметризуется количеством раундов k. В каждом раунде случайным образом выбирается число a < n. Если НОД(a,n) > 1, то выносится решение, что n составное. Иначе проверяется справедливость сравнения <math>\textstyle a^{(n-1)/2} \equiv \left( {a\over n} \right) \pmod{n}</math>. Если оно не выполняется, то выносится решение, что n — составное. Если это сравнение выполняется, то a является свидетелем простоты числа n. Далее выбирается другое случайное a и процедура повторяется. После нахождения k свидетелей простоты в k раундах выносится заключение, что n является простым числом с вероятностью <math>\textstyle 1 - 2^{-k} </math> .
На псевдокоде алгоритм может быть записан следующим образом:
Вход: <math>n</math> > 2, тестируемое нечётное натуральное число;
<math>k</math>, параметр, определяющий точность теста.
Выход: составное, означает, что <math>n</math> точно составное;
вероятно простое, означает, что <math>n</math> вероятно является простым.
for i = 1, 2, ..., <math>k</math>:
<math>a</math> = случайное целое от 2 до <math>n - 1</math>, включительно;
если НОД(a, n) > 1, тогда:
вывести, что <math>n</math> — составное, и остановиться.
если <math>a^{(n-1)/2} \not\equiv \left( {a\over n} \right) \pmod{n}</math>, тогда:
вывести, что <math>n</math> — составное, и остановиться.
иначе вывести, что <math>n</math> — простое с вероятностью <math>\textstyle 1 - 2^{-k} </math>, и остановиться.
Пример применения алгоритма
Проверим число n = 19 на простоту. Выберем параметр точности k = 2.
k = 1
Выберем случайное число a = 11; 2 < a < n - 1
Проверим условие НОД(a,n)>1
НОД(11,19)=1; значит проверяем выполнение сравнения <math>\textstyle a^{(n-1)/2} \equiv \left( \frac{a}{n} \right)\pmod{n}</math>
<math> r = \left( \frac{a}{n} \right) = \left( \frac{11}{19} \right) = 1 </math>
<math>\textstyle s = a^{(n-1)/2} = 11^{(19-1)/2}\pmod{19} = 1 </math>
Получили, что <math>\textstyle r = s </math> поэтому переходим к следующей итерации
k = 2
Выберем случайное число a = 5; 2 < a < n - 1
Проверим условие НОД(a,n)>1
НОД(5,19)=1; значит проверяем выполнение сравнения <math>\textstyle a^{(n-1)/2} \equiv \left( \frac{a}{n} \right)\pmod{n}</math>
<math> r = \left( \frac{a}{n} \right) = \left( \frac{5}{19} \right) = 1 </math>
<math>\textstyle s = a^{(n-1)/2} = 5^{(19-1)/2}\pmod{19} = 1 </math>
<math>\textstyle r = s </math> и это была последняя итерация, отсюда делаем вывод, что 19 - простое число с вероятностью <math> 1 - 2^{-2} </math>
Вычислительная сложность и точность
- Точность по сравнению с другими вероятностными тестами на простоту (здесь k — число независимых раундов)
| название теста | вероятность(что число составное)[3] | примечания |
|---|---|---|
| Ферма | <math> 2^{-k} </math> | не распознает числа Кармайкла как составные |
| Леманна | <math> 2^{-k} </math> | |
| Соловея — Штрассена | <math> 2^{-k} </math> |
- Теоретическая сложность вычислений всех приведенных в таблице тестов оценивается как <math>O(\log^3n)</math> .Шаблон:Sfn
- Алгоритм требует <math>O(k \log_2 m)</math> операций над длинными целыми числами.[1]
- При реализации алгоритма, для снижения вычислительной сложности, числа a выбираются из интервала 0 < a < c < n, где c — константа равная максимально возможному значению натурального числа, помещающегося в одном регистре процессора.Шаблон:Sfn
Применение
Вероятностные тесты применяются в системах основанных на проблеме факторизации, например RSA или схема Рабина. Однако на практике степень достоверности теста Соловея — Штрассена не является достаточной, вместо него используется тест Миллера — Рабина. Более того, используются объединенные алгоритмы, например пробное деление и тест Миллера — Рабина, при правильном выборе параметров можно получить результаты лучше, чем при применении каждого теста по отдельности.[3]
Улучшение теста
В 2005 году на Международной конференции Bit+ «Informational Technologies −2005» А. А. Балабанов, А. Ф. Агафонов, В. А. Рыку предложили модернизированный тест Соловея — Штрассена. Тест Соловея — Штрассена основан на вычислении символа Якоби, что занимает время эквивалентное <math> \log_{2} n </math>. Идея улучшения состоит в том, чтобы в соответствии с теоремой квадратичной взаимности Гаусса, перейти к вычислению величины <math> \left( \frac{n}{a}\right) </math>,являющейся обратной символу Якоби, что является более простой процедурой.[4].
См. также
Примечания
Литература
Шаблон:Теоретико-числовые алгоритмы
- ↑ 1,0 1,1 Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ 3,0 3,1 Б. Шнайер Прикладная криптография — М. : ТРИУМФ, 2002 . — Глава 11.
- ↑ Балабанов А. А.,Агафонов А. Ф.,Рыку В. А.Алгоритм быстрой генерации ключей в криптографической системе RSA. Шаблон:Wayback — Вестник научно-технического развития, 2009 № 7(23). — С. 11.
