Эта статья входит в число добротных статей

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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

История[править | править вики-текст]

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

Применение[править | править вики-текст]

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

Принцип работы алгоритма[править | править вики-текст]

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

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

Пусть — простое число. Представим число в виде , где — нечётно. Тогда для любого из выполняется одно из условий:


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

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

и

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

У нечётных составных чисел существует, согласно теореме Рабина, не более свидетелей простоты, где  — функция Эйлера, а вероятность того, что случайно выбранное число окажется свидетелем простоты не менее 3/4[2][6].

Идея теста заключается в том, чтобы проверять для случайно выбранных чисел , являются ли они свидетелями простоты числа . Если на определённом шаге алгоритма было проверено чисел, и все они оказались свидетелями простоты, то вероятность того, что число составное не более [7].

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

Пример[править | править вики-текст]

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

  • a20·d mod n = 17455 mod 221 = 47 ≠ 1, n − 1
  • a21·d mod n = 174110 mod 221 = 220 = n − 1.

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

  • a20·d mod n = 13755 mod 221 = 188 ≠ 1, n − 1
  • a21·d mod n = 137110 mod 221 = 205 ≠ n − 1.

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

Алгоритм Миллера — Рабина[править | править вики-текст]

Реализация[править | править вики-текст]

Алгоритм Миллера — Рабина параметризуется количеством раундов r. Рекомендуется брать r порядка величины , где n — проверяемое число.

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

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

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

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

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

Сложность работы[править | править вики-текст]

Считая, что время умножения логарифмическое, используя быстрое умножение по модулю, сложность работы алгоритма , где  — количество раундов. Таким образом, время работы алгоритма полиномиально.

Однако, используя БПФ, возможно сократить время работы алгоритма до . В таком случае, если брать , где n — проверяемое число, то сложность работы алгоритма равна .[11]

Сильно псевдопростые числа[править | править вики-текст]

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

Например, сильно псевдопростые числа по основанию 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)

Примечания[править | править вики-текст]

  1. Miller, 1975.
  2. 1 2 Rabin, 1980.
  3. 1 2 Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Handbook of Applied Cryptography. — 5. — 2001. — С. 141. — 816 с. — ISBN 0-8493-8523-7.
  4. Томас Х. Кормен. Алгоритмы: вводный курс. — Москва: Вильямс, 2015. — С. 147. — 208 с. — ISBN 978-5-8459-1868-0.
  5. 1 2 Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ. — 3. — Москва: Вильямс, 2013. — С. 1012-1015. — 1328 с. — ISBN 978-5-8459-1794-2.
  6. Schoof, René (2004), "Four primality testing algorithms", Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, Cambridge University Press, ISBN 0-521-80854-5, <http://www.mat.uniroma2.it/~schoof/millerrabinpom.pdf> 
  7. Monier, Louis (1980), "Evaluation and comparison of two efficient probabilistic primality testing algorithms", Theoretical Computer Science Т. 12 (1): 97-108, DOI 10.1016/0304-3975(80)90007-9 
  8. F. Arnault (August 1995). «Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases». Journal of Symbolic Computation 20 (2): 151–161. DOI:10.1006/jsco.1995.1042.
  9. Baillie R., Wagstaff S. S. Lucas Pseudoprimes // Math. Comp. AMS, 1980. — Vol. 35, Iss. 152. — P. 1391—1417. — ISSN 0025-5718; 1088-6842doi:10.1090/S0025-5718-1980-0583518-6
  10. Damgård, I.; Landrock, P. & Pomerance, C. (1993), "Average case error estimates for the strong probable prime test", Mathematics of Computation Т. 61 (203): 177–194, doi:10.2307/2152945, <http://www.math.dartmouth.edu/~carlp/PDF/paper88.pdf> 
  11. Брюс Шнайер. Прикладная Криптография. — Москва: Триумф, 2013. — С. 298. — 816 с.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]