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

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

История


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

Применение


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

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


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

Лемма про квадратные корни единицы в конечном поле $\mathbb{Z_p:ПомалойтеоремеФерма:a^{n-1} \equiv 1\pmod{n}.Будемизвлекатьквадратныекорниизчислаa^{n-1}$ Используя доказанную выше лемму, на каждом шаге у нас будет получаться число 1 или -1. Если на каком-то шаге у нас получится -1, то выполняется второе из равенств. Иначе на очередном шаге an12s=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 простым. Запишем как 22·55, таким образом s = 2 и d = 55. Произвольно выберем число a такое, что 0 \textless a \textless n, допустим a = 174. Переходим к вычислениям:

  • a2\textsuperscript0·d mod n = 17455 mod 221 = 47 ≠ 1, n − 1
  • a2\textsuperscript1·d mod n = 174110 mod 221 = 220 = n − 1.

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

  • a2\textsuperscript0·d mod n = 13755 mod 221 = 188 ≠ 1, n − 1
  • a2\textsuperscript1·d mod n = 137110 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\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\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\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 вероятность объявления составного числа вероятно простым существенно меньше чем 4k. Дамгард, Лэндрок и Померандс вычислили некоторые точные границы границы ошибок и предложили метод выбора значения k для получения нужной границы ошибки. Такие границы могут, например, использоваться для генерации вероятно простых чисел. Однако, они не должны использоваться для проверки простых чисел неизвестного происхождения, поскольку в криптографических системах взломщик может попытаться подставить псевдопростое число, в той ситуации когда требуется простое число. В таких случаях можно положиться только на ошибку 4k.

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


 Считая, что время умножения логарифмическое, используя быстрое умножение по модулю, сложность работы алгоритма 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