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

Тест Миллера — Рабина — это вероятностный полиномиальный тест простоты, предназначенный для определения того, является ли натуральное число составным или, вероятно, простым. Алгоритм основан на проверке свойств чисел, вытекающих из малой теоремы Ферма и свойств квадратичных вычетов. В отличие от детерминированных тестов (например, решета Эратосфена), тест Миллера — Рабина не даёт абсолютной гарантии простоты, но позволяет с высокой степенью достоверности отличить простые числа от составных. Тест широко используется в криптографии, в частности, при генерации больших простых чисел для алгоритмов RSA и Диффи — Хеллмана.

История

Тест был предложен американским математиком Гари Миллером в 1976 году. Первоначальная версия Миллера была детерминированной, однако её корректность зависела от недоказанной обобщённой гипотезы Римана (ОГР). В 1980 году израильский учёный Михаэль Рабин модифицировал алгоритм, сделав его вероятностным и устранив зависимость от ОГР. Рабин показал, что если выбрать несколько случайных оснований проверки, то вероятность ошибки может быть сделана сколь угодно малой. С тех пор тест Миллера — Рабина стал одним из наиболее практичных и распространённых методов проверки чисел на простоту.

Математические основы

Тест опирается на два ключевых свойства простых чисел:

1. Малая теорема Ферма: Если \( p \) — простое число и \( a \) — целое число, не кратное \( p \), то \( a^{p-1} \equiv 1 \pmod{p} \).
2. Свойство квадратичных вычетов: Если \( p \) — простое нечётное число, то сравнение \( x^2 \equiv 1 \pmod{p} \) имеет только два решения: \( x \equiv 1 \) и \( x \equiv -1 \).

Из второго свойства следует, что если для некоторого числа \( n \) существует такое \( a \), что \( a^2 \equiv 1 \pmod{n} \), но \( a \not\equiv \pm 1 \pmod{n} \), то \( n \) — составное. Такое \( a \) называется нетривиальным квадратным корнем из единицы по модулю \( n \). Нахождение нетривиального корня является свидетельством составности числа.

Тест Миллера — Рабина использует представление числа \( n-1 \) в виде \( n-1 = d \cdot 2^s \), где \( d \) — нечётное число, а \( s \geq 0 \). Затем для выбранного основания \( a \) вычисляется последовательность:

1. \( x_0 = a^d \mod n \)
2. \( x_1 = x_0^2 \mod n \)
3. \( x_2 = x_1^2 \mod n \)

...

1. \( x_s = x_{s-1}^2 \mod n = a^{n-1} \mod n \)

Если \( n \) простое, то в силу малой теоремы Ферма \( x_s \) должно быть равно 1. Кроме того, если на каком-либо шаге \( x_k = 1 \), а предыдущее значение \( x_{k-1} \) не равно \( \pm 1 \), то это означает нахождение нетривиального корня, и \( n \) — составное.

Алгоритм

Алгоритм принимает на вход нечётное число \( n > 2 \) (чётные числа, кроме 2, сразу отбрасываются) и параметр надёжности \( k \), определяющий количество испытаний. Если \( n = 2 \), оно сразу признаётся простым. Если \( n \) чётное или меньше 2, оно составное.

1. Представить \( n-1 \) как \( d \cdot 2^s \), где \( d \) — нечётное.
2. Повторить \( k \) раз:

• Выбрать случайное целое число \( a \) в интервале \( [2, n-2] \).
• Вычислить \( x = a^d \mod n \).
• Если \( x = 1 \) или \( x = n-1 \), перейти к следующей итерации (число не опровергнуто).
• Для \( r \) от 1 до \( s-1 \):
• \( x = x^2 \mod n \).
• Если \( x = n-1 \), перейти к следующей итерации.
• Если \( x = 1 \), то число \( n \) — составное (найден нетривиальный корень).
• Если цикл завершился без обнаружения \( n-1 \), число \( n \) — составное.

1. Если после \( k \) итераций не найдено свидетельств составности, число объявляется вероятно простым.

Вероятность ошибки

Каждое испытание со случайным основанием \( a \) может дать один из трёх результатов:

• Свидетель простоты — \( a \) не доказывает составность.
• Свидетель составности — \( a \) доказывает, что \( n \) составное.

Для составного нечётного числа \( n \) доля свидетелей составности среди всех чисел \( a \) в интервале \( [2, n-2] \) составляет не менее \( 3/4 \). Это означает, что вероятность того, что одно случайное основание не обнаружит составность, не превышает \( 1/4 \). После \( k \) независимых испытаний вероятность того, что составное число будет ошибочно признано простым, не превышает \( (1/4)^k \).

На практике для криптографических приложений обычно выбирают \( k = 20 \), что даёт вероятность ошибки менее \( 10^{-12} \). Для ещё большей надёжности можно увеличить \( k \) до 40 или 64.

Примеры работы

Пример 1: Простое число (n = 17)

\( n = 17 \), \( n-1 = 16 = 1 \cdot 2^4 \), \( d = 1, s = 4 \).

Выберем случайное основание, например \( a = 3 \).

1. \( x_0 = 3^1 \mod 17 = 3 \)
2. \( x_1 = 3^2 = 9 \mod 17 = 9 \)
3. \( x_2 = 9^2 = 81 \mod 17 = 13 \) (так как \( 81 - 4\cdot 17 = 81 - 68 = 13 \))
4. \( x_3 = 13^2 = 169 \mod 17 = 16 \) (так как \( 169 - 9\cdot 17 = 169 - 153 = 16 \)) — это \( n-1 \).

Условие \( x_r = n-1 \) выполнено, поэтому \( a = 3 \) является свидетелем простоты для \( n = 17 \). После нескольких таких испытаний (если все они дают аналогичный результат) число признаётся вероятно простым.

Пример 2: Составное число (n = 15, число Кармайкла)

\( n = 15, n-1 = 14 = 7 \cdot 2^1, d = 7, s = 1 \).

Выберем основание \( a = 2 \):

1. \( x_0 = 2^7 \mod 15 = 128 \mod 15 = 8 \)
2. \( x_1 = 8^2 \mod 15 = 64 \mod 15 = 4 \)

Ни одно из условий \( x = 1 \) или \( x = n-1 = 14 \) не выполняется. Число 15 объявляется составным. Действительно, \( 15 = 3 \times 5 \).

Достоинства и недостатки

Достоинства

• Высокая скорость: время выполнения пропорционально \( O(k \log^3 n) \), что позволяет проверять тысячи чисел в секунду, включая числа длиной в сотни десятичных знаков.
• Простота реализации: алгоритм легко программируется на любом языке.
• Управляемая точность: вероятность ошибки экспоненциально убывает с ростом числа испытаний.
• Отсутствие ложноположительных результатов: если тест объявил число составным, это всегда верно. Ошибки возможны только в сторону «вероятно простое» для составных чисел.

Недостатки

• Вероятностная природа: в отличие от теста AKS, тест Миллера — Рабина не даёт абсолютной гарантии простоты. Для криптографических задач это обычно приемлемо, но для математических доказательств требуется дополнительная верификация.
• Чувствительность к качеству генератора случайных чисел: плохой ГСЧ может снизить эффективную надёжность теста.
• Не применим к числам Мерсенна: для чисел вида \( 2^p - 1 \) существуют более эффективные специализированные тесты (тест Люка — Лемера).

Применение

Основная область применения теста Миллера — Рабина — криптография. Он используется:

• При генерации ключей для алгоритмов RSA, DSA, ECDSA.
• В протоколах Диффи — Хеллмана для выбора безопасных простых чисел.
• В системах цифровой подписи и шифрования с открытым ключом.
• В стандартах криптографической защиты, таких как ГОСТ Р 34.10-2012 и NIST SP 800-89.

Кроме того, тест применяется в теории чисел для быстрой проверки больших чисел на простоту перед более сложными детерминированными тестами.

Варианты и улучшения

• Тест Миллера — Рабина с фиксированными основаниями: для чисел определённого размера можно использовать небольшой набор оснований, гарантирующих детерминированную проверку. Например, для \( n < 2^{64} \) достаточно оснований \( \{2, 3, 5, 7, 11, 13\} \).
• Комбинированные тесты: часто тест Миллера — Рабина используется вместе с тестом Люка (например, тест Baillie-PSW), что повышает надёжность без существенного увеличения времени.
• Параллельные реализации: алгоритм легко распараллеливается, что ускоряет проверку больших наборов чисел.

Источники

• Miller, G. (1976). «Riemann's Hypothesis and Tests for Primality». Journal of Computer and System Sciences.
• Rabin, M. O. (1980). «Probabilistic algorithm for testing primality». Journal of Number Theory.
• Crandall, R., Pomerance, C. (2005). «Prime Numbers: A Computational Perspective». Springer.
• Menezes, A., van Oorschot, P., Vanstone, S. (1996). «Handbook of Applied Cryptography». CRC Press.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). «Introduction to Algorithms». MIT Press.