Тест Миллера — Рабина

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

История

Алгоритм Миллера-Рабина является модификацией алгоритма Миллера, разработанного Гари Миллером в 1976 году. Алгоритм Миллера является детерминированным, но его корректность опирается на недоказанную расширенную гипотезу Римана. Майкл Рабин модифицировал его в 1980 году. Алгоритм Миллера — Рабина не зависит от справедливости гипотезы, но является вероятностным.

Применение

Так как криптостойкость многих алгоритмов шифрования основывается на секретных ключах, для создания которых необходимы простые числа (например, так работает шифр RSA), то при создании таких ключей важно уметь достаточно быстро проверять большие числа на простоту. Вероятностные тесты простоты, такие как тест Миллера-Рабина и Тест Соловея — Штрассена, показывают большую эффективность использования и простоту выражения по сравнению с детерминированными тестами. Алгоритм Миллера-Рабина позволяет выполнять проверку за малое время и давать при этом достаточно малую вероятность того, что число на самом деле является составным.

Принцип работы алгоритма

Как и тесты Ферма и Соловея — Штрассена, тест Миллера — Рабина опирается на проверку ряда равенств, которые выполняются для простых чисел. Если хотя бы одно такое равенство не выполняется, это доказывает что число составное.

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

Пусть $n$ — простое число и $n-1=2^{s}d$, где $d$ — нечётно. Тогда для любого $a$ из $\mathbb {Z} _{n}$ выполняется хотя бы одно из условий:

1. $a^{d}\equiv 1{\pmod {n}}$
2. Существует целое число $r<s$ такое что $a^{2^{r}d}\equiv -1{\pmod {n}}$

Доказательство

Лемма про квадратные корни единицы в конечном поле $\mathbb {Z} _{p}$:

В конечном поле $\mathbb {Z} _{p}$ (для простого $p$) не существует квадратных корней из единицы, кроме чисел 1, -1

Доказательство

Пусть:

${a}\equiv {\sqrt {1}}{\pmod {p}}$

Тогда:

$a^{2}\equiv 1{\pmod {p}}$

$a^{2}{-1}\equiv 0{\pmod {p}}$

$(a+1)(a-1)\equiv 0{\pmod {p}}$

По лемме Евклида:

${\bigg [}{\begin{matrix}{a-1}\equiv {0}{\pmod {p}}\\{a+1}\equiv {0}{\pmod {p}}\end{matrix}}$

${\bigg [}{\begin{matrix}{a}\equiv {1}{\pmod {p}}\\{a}\equiv {-1}{\pmod {p}}\end{matrix}}$

 

По малой теореме Ферма:

$a^{n-1}\equiv 1{\pmod {n}}.$

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

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

В случае когда выполняется контрапозиция доказанного утверждения, то есть если найдётся число $a$ такое, что:

$a^{d}\not \equiv 1{\pmod {n}}$

и

$\forall r:\ 0\leq r\leq s-1:\ a^{2^{r}d}\not \equiv -1{\pmod {n}},$

то число $n$ не является простым. В этом случае число $a$ называют свидетелем того, что число $n$ составное.

У нечётных составных чисел $n$ существует, согласно теореме Рабина, не более $\varphi (n)/4$ свидетелей простоты, где $\varphi (n)$ — функция Эйлера, таким образом вероятность того, что случайно выбранное число $a$ окажется свидетелем простоты, меньше 1/4.

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

Для проверки больших чисел принято выбирать числа $a$ случайными, так как распределение свидетелей простоты и свидетелей составного числа среди чисел 1, 2, …, n − 1 заранее неизвестно. В частности Арнольт приводит 397-разрядное составное число, для которого все числа меньше 307 являются свидетелями простоты.

Пример

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

• a^20·d mod n = 174⁵⁵ mod 221 = 47 ≠ 1, n − 1
• a^21·d mod n = 174¹¹⁰ mod 221 = 220 = n − 1.

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

• a^20·d mod n = 137⁵⁵ mod 221 = 188 ≠ 1, n − 1
• a^21·d mod n = 137¹¹⁰ mod 221 = 205 ≠ n − 1.

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

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

Реализация

Алгоритм Миллера — Рабина параметризуется количеством раундов r. Рекомендуется брать r порядка величины $\log _{2}(n)$, где n — проверяемое число.

Для данного n находятся такие целое число s и целое нечётное число t, что $n-1=2^{s}t$. Выбирается случайное число a, 1 < a < n. Если a не является свидетелем простоты числа n, то выдаётся ответ «n — составное», и алгоритм завершается. Иначе, выбирается новое случайное число a и процедура проверки повторяется. После нахождения r свидетелей простоты, выдаётся ответ «n — вероятно простое», и алгоритм завершается.

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

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

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

Также для больших значений n вероятность объявления составного числа вероятно простым существенно меньше чем 4^−k. Дамгард, Лэндрок и Померандс вычислили некоторые точные границы ошибок и предложили метод выбора значения k для получения нужной границы ошибки. Такие границы могут, например, использоваться для генерации вероятно простых чисел. Однако, они не должны использоваться для проверки простых чисел неизвестного происхождения, поскольку в криптографических системах взломщик может попытаться подставить псевдопростое число, в той ситуации, когда требуется простое число. В таких случаях можно положиться только на ошибку 4^−k.

Сложность работы

Считая, что время умножения логарифмическое, используя быстрое умножение по модулю, сложность работы алгоритма $O(k\log ^{3}n)$, где $k$ — количество раундов. Таким образом, время работы алгоритма полиномиально.

Однако, используя БПФ, возможно сократить время работы алгоритма до $O(k\log ^{2}(n)\log(\log(n))\log(\log(\log(n))))={\widetilde {O}}(k\log ^{2}(n))$. В таком случае, если брать $k=\log _{2}(n)$, где n — проверяемое число, то сложность работы алгоритма равна ${\widetilde {O}}(\log ^{3}n)$.

Сильно псевдопростые числа

Если число a является свидетелем простоты составного нечётного числа n по Миллеру, то число n, в свою очередь, называется сильно псевдопростым по основанию a. Если число n является сильно псевдопростым по основанию a, то оно также является псевдопростым Ферма по основанию a, так и Псевдопростым Эйлера — Якоби по основанию a.

Например, сильно псевдопростые числа по основанию 2 образуют последовательность:

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, … (последовательность A001262 в OEIS)

а по основанию 3 — последовательность:

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, … (последовательность A020229 в OEIS)

Литература

• Miller G. Riemann's Hypothesis and Tests for Primality (англ.) // STOC '75: Proceedings of seventh annual ACM symposium on Theory of computing — New York City: ACM, 1975. — P. 234—239. — doi:10.1145/800116.803773
• Rabin M. O. Probabilistic algorithm for testing primality (англ.) // Journal of Number Theory / D. Goss — Elsevier BV, 1980. — Vol. 12, Iss. 1. — P. 128–138. — ISSN 0022-314X; 1096-1658 — doi:10.1016/0022-314X(80)90084-0
• Baillie R., Samuel S. Wagstaff, Jr. Lucas Pseudoprimes (англ.) // Mathematics of Computation — AMS, 1980. — Vol. 35, Iss. 152. — P. 1391—1417. — ISSN 0025-5718; 1088-6842 — doi:10.1090/S0025-5718-1980-0583518-6
• Monier L. Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms (англ.) // Theoretical Computer Science — Elsevier BV, 1980. — Vol. 12, Iss. 1. — P. 97—108. — ISSN 0304-3975; 1879-2294 — doi:10.1016/0304-3975(80)90007-9
• Damgård I., Landrock P., Pomerance C. Average Case Error Estimates for the Strong Probable Prime Test (англ.) // Mathematics of Computation — AMS, 1993. — Vol. 61, Iss. 203. — P. 177—194. — ISSN 0025-5718; 1088-6842 — doi:10.2307/2152945
• Arnault F. Constructing Carmichael Numbers which are Strong Pseudoprimes to Several Bases (англ.) // Journal of Symbolic Computation — Elsevier BV, 1995. — Vol. 20, Iss. 2. — P. 151—161. — ISSN 0747-7171; 1095-855X — doi:10.1006/JSCO.1995.1042
• Menezes A. J., Oorschot P. v., Vanstone S. A. Handbook of Applied Cryptography (англ.) — Boca Raton: CRC Press, 1997. — 816 p. — (Discrete Mathematics and Its Applications) — ISBN 978-0-8493-8523-0
• Schoof R. Four Primality Testing Algorithms (англ.) // Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography / J. P. Buhler, P. Stevenhagen — Cambridge: Cambridge University Press, 2008. — P. 69—81. — (Mathematical Sciences Research Institute Publications; Vol. 44) — ISBN 978-0-521-80854-5
• Кормен Т. Х. Алгоритмы: Вводный курс / пер. И. Красиков — М.: Вильямс, 2015. — 208 с. — ISBN 978-5-8459-1868-0, 978-5-8459-2073-7

Ссылки

• Ю. В. Нестеренко. Глава 4.4. Как отличить составное число от простого // Введение в криптографию / Под ред. В. В. Ященко. — Питер, 2001. — 288 с. — ISBN 5-318-00443-1. Архивная копия от 25 февраля 2008 на Wayback Machine
• Примеры реализации алгоритма на многих языках программирования
• С. Б. Гашков. Упрощённое обоснование вероятностного теста Миллера — Рабина для проверки простоты чисел.
• Weisstein, Eric W. Rabin-Miller Strong Pseudoprime Test (англ.) на сайте Wolfram MathWorld.
• "SPRP records"
• Crandall, R. and Pomerance, C. Probable primes and witnesses // Prime Numbers. — Springer-Verlag, 2001. — ISBN 978-0387252827.