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

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

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

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

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

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

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

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

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

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

Для данного m находятся такие целое число s и целое нечётное число t, что m − 1 = 2^st. Выбирается случайное число 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 то перейти на следующую итерацию цикла А
   для r = 1 .. s − 1
      x ← x2 mod m
      если x = 1 то вернуть составное
      если x = m − 1 то перейти на следующую итерацию цикла А
   вернуть составное
вернуть вероятно простое

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

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

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

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

Если число a является свидетелем простоты составного нечетного числа m, то число m в свою очередь называется сильно псевдопростым по основанию a. Если число m является сильно псевдопростым по основанию a, то оно также является псевдопростым по основанию a.

Ссылки

• «Как отличить составное число от простого», глава 4.4 из книги «Введение в криптографию» под редакцией В. В. Ященко
• С. Б. Гашков, «Упрощенное обоснование вероятностного теста Миллера — Рабина для проверки простоты чисел»
• Пример реализации на языке Python