Просмотр кода страницы Тест Миллера — Рабина

'''Тест Миллера — Рабина''' — [[класс BPP|вероятностный полиномиальный]] [[тест простоты]]. Тест Миллера — Рабина, наряду с [[Тест Ферма|тестом Ферма]] и [[Тест Соловея — Штрассена|тестом Соловея — Штрассена]], позволяет эффективно определить, является ли данное число [[Составное число|составным]]. Однако, с его помощью нельзя строго доказать [[Простое число|простоту числа]]. Тем не менее тест Миллера — Рабина часто используется в [[Криптография|криптографии]] для получения больших [[случайное простое число|случайных простых чисел]].

== История ==
Алгоритм Миллера-Рабина является модификацией [[Тест Миллера (теория чисел)|алгоритма Миллера]], разработанного [[Миллер, Гари|Гари Миллером]] в [[1976 год]]у. Алгоритм Миллера является [[Детерминированный алгоритм|детерминированным]], но его корректность опирается на недоказанную [[Гипотеза Римана|расширенную гипотезу Римана]]{{sfn|Miller|1975}}. [[Рабин, Майкл Озер|Майкл Рабин]] модифицировал его в [[1980 год]]у{{sfn|Rabin|1980}}. Алгоритм Миллера — Рабина не зависит от справедливости гипотезы, но является вероятностным.

== Применение ==
Так как криптостойкость многих алгоритмов шифрования основывается на секретных ключах, для создания которых необходимы простые числа (например, так работает шифр [[RSA]]), то при создании таких ключей важно уметь достаточно быстро проверять большие числа на простоту. Вероятностные тесты простоты, такие как тест Миллера-Рабина и [[Тест Соловея — Штрассена]], показывают большую эффективность использования и простоту выражения по сравнению с детерминированными тестами{{sfn|Menezes, Oorschot, Vanstone|1996|pp=141}}. Алгоритм Миллера-Рабина позволяет выполнять проверку за малое время и давать при этом достаточно малую вероятность того, что число на самом деле является составным.{{sfn|Кормен|2015|страницы=147}}

== Принцип работы алгоритма ==
Как и тесты [[Тест Ферма|Ферма]] и [[Тест Соловея — Штрассена|Соловея — Штрассена]], тест Миллера — Рабина опирается на проверку ряда равенств, которые выполняются для простых чисел. Если хотя бы одно такое равенство не выполняется, это доказывает что число составное<ref name="algorithms"/>.

Для теста Миллера — Рабина используется следующее утверждение:

{{Теорема|1=Пусть <math>n</math> — простое число и <math>n-1 = 2^s d</math>, где <math>d</math> — нечётно. Тогда для любого <math>a</math> из <math>\mathbb{Z}_n</math> выполняется хотя бы одно из условий:
# <math>a^{d} \equiv 1\pmod{n} </math>
# Существует целое число <math>r < s</math> такое что <math>a^{2^{r}d} \equiv -1\pmod{n} </math>
}}

{{Доказ1|qed=&nbsp;|

: '''Лемма про квадратные корни единицы в конечном поле <math>\mathbb{Z}_p</math>:'''
{{Теорема|1=В конечном поле <math>\mathbb{Z}_p</math> (для простого <math>p</math>) не существует квадратных корней из единицы, кроме чисел ''1'', ''-1''}}

{{Доказ1|qed=&nbsp;|
Пусть:
: <math>{a} \equiv {\sqrt{1} }\pmod{p} </math>
Тогда:
: <math>a^{2} \equiv 1\pmod{p} </math>
: <math>a^{2} {-1}\equiv 0\pmod{p} </math>
: <math> (a + 1)( a - 1) \equiv 0\pmod{p}</math>
По [[Лемма Евклида|лемме Евклида]]:
: <math>\bigg [ \begin{matrix} {a - 1} \equiv {0}\pmod{p} \\ {a + 1} \equiv {0}\pmod{p} \end{matrix} </math>

: <math>\bigg [ \begin{matrix} {a}\equiv {1}\pmod{p} \\ {a}\equiv {-1}\pmod{p} \end{matrix} </math>
}}
По [[Малая теорема Ферма|малой теореме Ферма]]:
: <math>a^{n-1} \equiv 1\pmod{n}.</math>

Будем извлекать квадратные корни из числа <math>a^{n-1}</math>.
По доказанной выше лемме, на каждом шаге у нас будет получаться число ''1'' или ''-1'' по модулю <math>n</math>. 
Если на каком-то шаге у нас получится ''-1'', то выполняется второе из равенств. 
Иначе на последнем шаге <math>\sqrt[ {{2}^{s} } ]{a^{n-1} } =a^{d} </math> (т. к. <math>n-1 = 2^s d</math>) т. е. выполнится первое равенство.
}}

Если это утверждение (условие 1 или 2) выполняется для некоторых чисел <math>a</math> и <math>n</math> (не обязательно простого), то число <math>a</math> называют '''свидетелем простоты''' числа <math>n</math> по Миллеру, а само число <math>n</math> — [[Вероятно простое число|вероятно простым]]. (При случайно выбранном <math>a</math> вероятность ошибочно принять составное число за простое составляет 25 %, но её можно уменьшить, выполнив проверки для других <math>a</math>.)

В случае когда выполняется [[контрапозиция]] доказанного утверждения, то есть если найдётся число <math>a</math> такое, что:
: <math>a^{d} \not\equiv 1\pmod{n}</math>
и
: <math>\forall r:\ 0\le r\le s-1:\ a^{2^rd} \not\equiv -1\pmod{n},</math>
то число <math>n</math> не является простым. В этом случае число <math>a</math> называют свидетелем того, что число <math>n</math> составное.

У нечётных составных чисел <math>n</math> существует, согласно '''теореме Рабина''', не более <math>\varphi(n)/4</math> свидетелей простоты, где <math>\varphi(n)</math> — [[функция Эйлера]], таким образом вероятность того, что случайно выбранное число <math>a</math> окажется свидетелем простоты, меньше 1/4{{sfn|Rabin|1980}}{{sfn|Schoof|2008}}.

Идея теста заключается в том, чтобы проверять для случайно выбранных чисел <math>a<n</math>, являются ли они свидетелями простоты числа <math>n</math>. Если найдётся свидетель того, что число составное, то число действительно является составным. Если было проверено <math>k</math> чисел, и все они оказались свидетелями простоты, то число считается простым. Для такого алгоритма вероятность принять составное число за простое будет меньше <math>(1/4)^{k}</math>{{sfn|Monier|1980}}.

Для проверки больших чисел принято выбирать числа <math>a</math> случайными, так как распределение свидетелей простоты и свидетелей составного числа среди чисел 1, 2, …, n − 1 заранее неизвестно. В частности Арнольт{{sfn|Arnault|1995}} приводит 397-разрядное составное число, для которого все числа меньше 307 являются свидетелями простоты.

== Пример ==

Предположим, мы хотим определить, является ли ''n'' = 221 простым. Запишем {{nowrap|''n'' − 1 {{=}} 220}} как 2<sup>2</sup>·55, таким образом ''s'' = 2 и ''d'' = 55. Произвольно выберем число ''a'' такое, что 0 < ''a'' < ''n'', допустим ''a'' = 174. Переходим к вычислениям:

* ''a''<sup>2<sup>0</sup>·''d''</sup> mod ''n'' = 174<sup>55</sup> mod 221 = 47 ≠ 1, ''n'' − 1
* ''a''<sup>2<sup>1</sup>·''d''</sup> mod ''n'' = 174<sup>110</sup> mod 221 = 220 = ''n'' − 1.

Так как 220 ≡ −1 mod ''n'', число 221 или простое, или 174 — ложный свидетель простоты числа 221. Возьмём другое произвольное ''a'', на этот раз выбрав ''a'' = 137:

* ''a''<sup>2<sup>0</sup>·''d''</sup> mod ''n'' = 137<sup>55</sup> mod 221 = 188 ≠ 1, ''n'' − 1
* ''a''<sup>2<sup>1</sup>·''d''</sup> mod ''n'' = 137<sup>110</sup> mod 221 = 205 ≠ ''n'' − 1.

Так как 137 свидетель того, что 221 составное, число 174 на самом деле было ложным свидетелем простоты. Заметим, что алгоритм ничего не говорит нам о множителях числа 221 (которые равны 13 и 17). Однако в некоторых случаях дополнительные вычисления помогают получить множители числа.{{sfn|Baillie, Wagstaff|1980}}

== Алгоритм Миллера — Рабина ==

=== Реализация ===
Алгоритм Миллера — Рабина параметризуется количеством раундов ''r''. Рекомендуется брать ''r'' порядка величины <math>\log_2(n)</math>, где ''n'' — проверяемое число.

Для данного ''n'' находятся такие целое число ''s'' и целое нечётное число ''t'', что <math>n-1 = 2^s t</math>. Выбирается случайное число ''a'', 1 < ''a'' < ''n''. Если ''a'' не является свидетелем простоты числа ''n'', то выдаётся ответ ''«n — составное»'', и алгоритм завершается. Иначе, выбирается новое случайное число ''a'' и процедура проверки повторяется. После нахождения ''r'' свидетелей простоты, выдаётся ответ ''«n — вероятно простое»'', и алгоритм завершается<ref name="algorithms">{{Книга|автор = Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн|заглавие = Алгоритмы: построение и анализ|издание = 3|место = Москва|издательство = Вильямс|год = 2013|страницы = 1012—1015|страниц = 1328|isbn = 978-5-8459-1794-2}}</ref>.

Алгоритм может быть записан на [[Псевдокод (язык описания алгоритмов)|псевдокоде]] следующим образом:
 
  '''Ввод''': ''n'' > 2, нечётное натуральное число, которое необходимо проверить на простоту;
        ''k'' — количество раундов.
 '''Вывод''': ''составное'', означает, что ''n'' является составным числом;
        ''вероятно простое'', означает, что ''n'' с высокой вероятностью является простым числом.
 Представить ''n'' − 1 в виде 2<sup>''s''</sup>·''t'', где ''t'' нечётно, можно сделать последовательным делением ''n'' - 1 на 2.
 <u>цикл</u> А: повторить ''k'' раз:
    Выбрать случайное целое число ''a'' в отрезке [2, ''n'' − 2]
    ''x'' ← ''a''<sup>''t''</sup> mod ''n'', вычисляется с помощью алгоритма [[Алгоритмы быстрого возведения в степень по модулю|возведения в степень по модулю]]
    <u>если</u> ''x'' = 1 или ''x'' = ''n'' − 1, <u>то</u> перейти на следующую итерацию цикла А
    <u>цикл</u> B: повторить ''s'' − 1 раз
       ''x'' ← ''x''<sup>2</sup> mod ''n''
       <u>если</u> ''x'' = 1, <u>то</u> <u>вернуть</u> ''составное''
       <u>если</u> ''x'' = ''n'' − 1, <u>то</u> перейти на следующую итерацию цикла A
    <u>вернуть</u> ''составное''
 <u>вернуть</u> ''вероятно простое''

Из теоремы Рабина следует, что если ''k'' случайно выбранных чисел оказались свидетелями простоты числа ''n'', то вероятность того, что ''n'' составное, не превосходит <math>4^{-k}</math>.

Также для больших значений ''n'' вероятность объявления составного числа вероятно простым существенно меньше чем 4<sup>−''k''</sup>. Дамгард, Лэндрок и Померандс{{sfn|Damgård, Landrock, Pomerance|1993}} вычислили некоторые точные границы ошибок и предложили метод выбора значения k для получения нужной границы ошибки. Такие границы могут, например, использоваться для генерации вероятно простых чисел. Однако, они не должны использоваться для проверки простых чисел неизвестного происхождения, поскольку в криптографических системах взломщик может попытаться подставить псевдопростое число, в той ситуации, когда требуется простое число. В таких случаях можно положиться только на ошибку 4<sup>−''k''</sup>.

=== Сложность работы ===
Считая, что время умножения логарифмическое, используя [[Возведение в степень по модулю#Алгоритм быстрого возведения в степень по модулю|быстрое умножение по модулю]], сложность работы алгоритма <math>O(k\log^3n)</math>, где <math>k</math> — количество раундов. Таким образом, время работы алгоритма полиномиально.

Однако, используя [[БПФ]], возможно сократить время работы алгоритма до <math>O(k\log^2(n)\log(\log(n))\log(\log(\log(n)))) = \widetilde O(k\log^2(n))</math>. В таком случае, если брать <math>k = \log_2(n)</math>, где n — проверяемое число, то сложность работы алгоритма равна <math>\widetilde O(\log^3n)</math>.<ref>{{Книга|автор = Брюс Шнайер |заглавие = Прикладная Криптография |издание = |место = Москва |издательство = Триумф |год = 2013 |страницы = 298 |страниц = 816 |isbn =}}</ref>

== Сильно псевдопростые числа ==
Если число ''a'' является свидетелем простоты ''составного'' нечётного числа ''n'' по Миллеру, то число ''n'', в свою очередь, называется '''сильно псевдопростым''' по основанию ''a''. Если число ''n'' является сильно псевдопростым по основанию ''a'', то оно также является [[Псевдопростое число Ферма|псевдопростым Ферма]] по основанию ''a'', так и [[Псевдопростое число#Псевдопростые Эйлера — Якоби|Псевдопростым Эйлера — Якоби]] по основанию ''a''.{{sfn|Menezes, Oorschot, Vanstone|1996|pp=141}}

Например, сильно псевдопростые числа по основанию 2 образуют последовательность:
: 2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, … ({{OEIS|A001262}})
а по основанию 3 — последовательность:
: 121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, … ({{OEIS|A020229}})

== Примечания ==
{{примечания|3}}

== Литература ==
* {{source|Q21950754|ref=Miller|ref-year=1975}} <!-- Riemann’s Hypothesis and Tests for Primality // STOC '75 -->
* {{source|Q21950792|ref=Rabin|ref-year=1980}} <!-- Rabin M. O. Probabilistic algorithm for testing primality // J. Number Theor. -->
* {{source|Q21950824|ref=Baillie, Wagstaff|ref-year=1980}} <!-- Lucas Pseudoprimes -->
* {{source|Q27940855|ref=Monier|ref-year=1980}} <!-- Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms // Theoretical Computer Science -->
* {{source|Q27940868|ref=Damgård, Landrock, Pomerance|ref-year=1993}} <!-- Average Case Error Estimates for the Strong Probable Prime Test // Math. Comp. -->
* {{source|Q27940862|ref=Arnault|ref-year=1995}} <!-- Constructing Carmichael Numbers which are Strong Pseudoprimes to Several Bases // Journal of Symbolic Computation -->
* {{source|Q21725116|ref=Menezes, Oorschot, Vanstone|ref-year=1996}} <!-- Handbook of Applied Cryptography -->
* {{source|Q27940816|ref=Schoof|ref-year=2008}} <!-- Four Primality Testing Algorithms // Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography -->
* {{source|Q27940937|ref=Кормен|ref-year=2015}} <!-- Алгоритмы: Вводный курс -->

== Ссылки ==
* {{книга |автор=Ю. В. Нестеренко. |часть=Глава 4.4. Как отличить составное число от простого |заглавие=Введение в криптографию |ответственный=Под ред. В.&nbsp;В.&nbsp;Ященко |год=2001 |издательство=Питер |isbn=5-318-00443-1 |страниц=288 |ссылка=http://nature.web.ru/db/msg.html?mid=1157083&uri=book.html|ссылка часть=http://nature.web.ru/db/msg.html?mid=1157083&uri=node32.html }} {{Wayback|url=http://nature.web.ru/db/msg.html?mid=1157083&uri=book.html |date=20080225102710 }}
* [http://rosettacode.org/wiki/Miller-Rabin_primality_test Примеры реализации алгоритма на многих языках программирования]
* {{статья |автор=С.&nbsp;Б.&nbsp;Гашков |ссылка=http://new.math.msu.su/department/dm/dmmc/PUBL/Rab-mill.ps |заглавие=Упрощённое обоснование вероятностного теста Миллера&nbsp;— Рабина для проверки простоты чисел}}
* {{MathWorld|urlname=Rabin-MillerStrongPseudoprimeTest|title=Rabin-Miller Strong Pseudoprime Test}}
* [http://miller-rabin.appspot.com "SPRP records"]
* {{книга |автор=Crandall, R. and Pomerance, C. |часть=Probable primes and witnesses |заглавие=Prime Numbers |год=2001 |издательство=Springer-Verlag |isbn=978-0387252827}}

{{Внешние ссылки}}
{{Теоретико-числовые алгоритмы}}

{{Добротная статья|Теория информации и криптография}}

[[Категория:Тесты простоты]]