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

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

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

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

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

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

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

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

  1. a^{d} \equiv 1\pmod{p}
  2. \exists r, 0\le r\le s-1:\ a^{2^{r}d} \equiv -1\pmod{p}

Если это утверждение выполняется для некоторых чисел a и p, то число a называют свидетелем простоты числа p, а само число p — вероятно простым.

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

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

и

\forall r:\ 0\le r\le s-1:\ a^{2^rd} \not\equiv -1\pmod{n},

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

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

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

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

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

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

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

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

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

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

Изначальный алгоритм, предложенный Миллером, был детерминированным и состоял в проверке всех a от 2 до 2 \ln^2m. Алгоритм Миллера гарантированно распознает простые и составные числа при условии выполнения расширенной гипотезы Римана. Алгоритм Миллера — Рабина не зависит от справедливости гипотезы, но является вероятностным.

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

Если число a является свидетелем простоты составного нечётного числа m, то число m, в свою очередь, называется сильно псевдопростым по основанию a. Если число m является сильно псевдопростым по основанию 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)

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

  1. Miller, Gary L. (1976), "«Riemann's Hypothesis and Tests for Primality»", Journal of Computer and System Sciences Т. 13 (3): 300–317, DOI 10.1145/800116.803773 
  2. Rabin, Michael O. (1980), "«Probabilistic algorithm for testing primality»", Journal of Number Theory Т. 12 (1): 128–138, DOI 10.1016/0022-314X(80)90084-0 
  3. 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 

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