Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

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

История


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

Применение


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

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


 Как и тесты Ферма и Соловея — Штрассена, тест Миллера — Рабинаопирается на проверку ряда равенств, которые выполняются для простыхчисел. Если хотя бы одно такое равенство не выполняется, это доказываетчто число составное.
 Для теста Миллера — Рабина используется следующее утверждение:
 \{\{Доказ1\textbarqed= \textbar

Лемма про квадратные корни единицы в конечном поле$\mathbb{Z_p:ПомалойтеоремеФерма:a^{n-1} \equiv 1\pmod{n}.Будемизвлекатьквадратныекорниизчислаa^{n-1}$ Используя доказаннуювыше лемму, на каждом шаге у нас будет получаться число 1 или-1. Если на каком-то шаге у нас получится -1, товыполняется второе из равенств. Иначе на очередном шаге2san1=ad (т. к. n1=2sd) т. е.выполнится первое равенство. \}\}
 Если это утверждение (условие 1 или 2) выполняется для некоторых чиселa и n (не обязательно простого), то число a называютсвидетелем простоты числа n по Миллеру, а само число n —вероятно простым. (При случайно выбранном a вероятность ошибочнопринять составное число за простое составляет 25 уменьшить, выполнив проверки для других a.)
 В случае когда выполняется контрапозиция доказанного утверждения, тоесть если найдется число a такое, что:

ad1(modn)
 и

r: 0rs1: a2rd1(modn),
 то число n не является простым. В этом случае число a называютсвидетелем того, что число n составное.
 У нечётных составных чисел n существует, согласно теоремеРабина, не более φ(n)/4 свидетелей простоты, гдеφ(n) — функция Эйлера, таким образом вероятность того, чтослучайно выбранное число a окажется свидетелем простоты, меньше 1/4.
 Идея теста заключается в том, чтобы проверять для случайно выбранныхчисел $a Для проверки больших чисел принято выбирать числа а случайными, так какраспределение свидетелей простоты и свидетелей составного числа средичисел 1, 2, \ldots, n − 1 заранее неизвестно. В частности Арнольтприводит 397-разрядное составное число, для которого все числа меньше307 являются свидетелями простоты.

Пример


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

  • a\textsuperscript2\textsuperscript0·d mod n = 174\textsuperscript55 mod 221 = 47 ≠ 1, n − 1
  • a\textsuperscript2\textsuperscript1·d mod n = 174\textsuperscript110 mod 221 = 220 = n − 1.

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

  • a\textsuperscript2\textsuperscript0·d mod n = 137\textsuperscript55 mod 221 = 188 ≠ 1, n − 1
  • a\textsuperscript2\textsuperscript1·d mod n = 137\textsuperscript110 mod 221 = 205 ≠ n − 1.

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

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


Реализация


 Алгоритм Миллера — Рабина параметризуется количеством раундовr. Рекомендуется брать r порядка величины log2(n), гдеn — проверяемое число.
 Для данного n находятся такие целое число s и целоенечётное число t, что n1=2st. Выбирается случайное числоa, 1 \textless a \textless n. Если a неявляется свидетелем простоты числа n, то выдаётся ответ«n — составное», и алгоритм завершается. Иначе, выбираетсяновое случайное число a и процедура проверки повторяется. Посленахождения r свидетелей простоты, выдаётся ответ «n —вероятно простое», и алгоритм завершается.
 Алгоритм может быть записан на псевдокоде следующим образом:
 \texttt \textttВвод\texttt: \textttn\texttt \textgreater 2, нечётное натуральное число, которое необходимо проверить на простоту;\\\texttt       \textttk\texttt — количество раундов.\\\textttВывод\texttt: \textttсоставное\texttt, означает, что \textttn\texttt является составным числом;\\\texttt       \textttвероятно\textttпростое\texttt, означает, что \textttn\texttt с высокой вероятностью является простым числом.\\\textttПредставить \textttn\texttt − 1 в виде 2\textsuperscript\texttts\texttt·\textttt\texttt, где \textttt\texttt нечётно, можно сделать последовательным делением \textttn\texttt - 1 на 2.\\\textttцикл\texttt А: повторить \textttk\texttt раз:\\\texttt   Выбрать случайное целое число \texttta\texttt в отрезке [2, \textttn\texttt − 2]\\\texttt   \textttx\texttt ← \texttta\textsuperscript\textttt\texttt mod \textttn\texttt, вычисляется с помощью алгоритма возведения в степень по модулю\\\texttt   \textttесли\texttt \textttx\texttt = 1 или \textttx\texttt = \textttn\texttt − 1, \textttто\texttt перейти на следующую итерацию цикла А\\\texttt   \textttцикл\texttt B: повторить \texttts\texttt − 1 раз\\\texttt      \textttx\texttt ← \textttx\textsuperscript\texttt2\texttt mod \textttn\\\texttt      \textttесли\texttt \textttx\texttt = 1, \textttто\texttt \textttвернуть\texttt \textttсоставное\\\texttt      \textttесли\texttt \textttx\texttt = \textttn\texttt − 1, \textttто\texttt перейти на следующую итерацию цикла A\\\texttt   \textttвернуть\texttt \textttсоставное\\\textttвернуть\texttt \textttвероятно\textttпростое
 Из теоремы Рабина следует, что если k случайно выбранных чиселоказались свидетелями простоты числа n, то вероятность того, чтоn составное, не превосходит 4k.
 Также для больших значений n вероятность объявления составногочисла вероятно простым существенно меньше чем4\textsuperscript−k. Дамгард, Лэндрок и Померандс вычислилинекоторые точные границы границы ошибок и предложили метод выборазначения k для получения нужной границы ошибки. Такие границы могут,например, использоваться для генерации вероятно простых чисел. Однако,они не должны использоваться для проверки простых чисел неизвестногопроисхождения, поскольку в криптографических системах взломщик можетпопытаться подставить псевдопростое число, в той ситуации когдатребуется простое число. В таких случаях можно положиться только наошибку 4\textsuperscript−k.

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


 Считая, что время умножения логарифмическое, используя быстрое умножениепо модулю, сложность работы алгоритма O(klog3n), где k —количество раундов. Таким образом, время работы алгоритма полиномиально.
 Однако, используя БПФ, возможно сократить время работы алгоритма доO(klog2(n)log(log(n))log(log(log(n))))=O(klog2(n)). В такомслучае, если брать k=log2(n), где n — проверяемое число, тосложность работы алгоритма равна O(log3n).

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


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

 2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281,74665, \ldots
 а по основанию 3 — последовательность:

 121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345,23521, 31621, \ldots