Тест Миллера

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

Алгоритм был разработан Гари Миллером в 1976 году и модифицирован Майклом Рабином в 1980 году.

Свидетели простоты и теорема Рабина

Пусть $~m$ — нечётное число большее 1. Число $~m-1$ однозначно представляется в виде $m-1 = 2^s \cdot t$, где $~t$ нечётно. Целое число $~a$, $~1 < a < m$, называется свидетелем простоты числа $~m$, если выполняется одно из условий:

• $~a^t\equiv 1\pmod m$

или

• существует целое число $~k$, $~0\leq k<s$, такое, что $~ a^{2^kt}\equiv m-1\pmod m.$

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

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

Алгоритм Миллера — Рабина параметризуется количеством раундов 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]
   x ← at mod m
   если x = 1 или x = m − 1, то перейти на следующую итерацию цикла А
   цикл B: повторить s − 1 раз
      x ← x2 mod m
      если x = 1, то вернуть составное
      если x = m − 1, то перейти на следующую итерацию цикла А
   вернуть составное
вернуть вероятно простое

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

Алгоритм Миллера

Основная статья: Тест Миллера (теория чисел)

Изначальный алгоритм, предложенный Миллером, был детерминированным и состоял в проверке всех a от $2$ до $70 \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)

Ссылки

• Rabin M. O. Probabilistic algorithm for testing primality (англ.) // Journal of Number Theory. — Elsevier Inc., 1980. — В. 1. — Т. 12. — С. 128-138. — ISSN 0022-314X. — DOI:10.1016/0022-314X(80)90084-0
• Ю. В. Нестеренко. Глава 4.4. Как отличить составное число от простого // Введение в криптографию / Под ред. В. В. Ященко. — Питер, 2001. — 288 с. — ISBN 5-318-00443-1
• С. Б. Гашков Упрощенное обоснование вероятностного теста Миллера — Рабина для проверки простоты чисел.
• Пример реализации на нескольких языках