Вероятностный тест простоты

Вероятностный тест простоты — это алгоритм, который определяет, является ли заданное натуральное число составным, с некоторой вероятностью ошибки (ложноположительного результата), либо, с высокой вероятностью, простым. В отличие от детерминированных тестов, которые дают абсолютно точный ответ о простоте числа, вероятностные тесты основаны на проверке свойств, выполняющихся для всех простых чисел, но не всегда выполняющихся для составных. Если число не удовлетворяет проверяемому свойству, оно гарантированно является составным. Если же свойство выполняется, число может быть либо простым, либо «сильным псевдопростым» — составным числом, которое обманывает тест. Вероятностные тесты широко применяются в криптографии, где требуется быстро генерировать большие простые числа (например, для алгоритмов RSA, Диффи — Хеллмана), и где допустима сколь угодно малая, но не нулевая вероятность ошибки.

История

Проблема эффективного распознавания простых чисел возникла задолго до появления компьютеров. Древнегреческие математики, такие как Эратосфен, разработали решето для нахождения всех простых чисел до заданного предела, но этот метод требовал перебора всех делителей и был неприменим для больших чисел. В XVII—XIX веках были открыты малая теорема Ферма и свойства квадратичных вычетов, которые легли в основу первых вероятностных тестов.

В 1976 году Гэри Миллер предложил детерминированный тест, основанный на расширенной гипотезе Римана, который позже был адаптирован Майклом Рабином в 1980 году в вероятностный тест Миллера — Рабина, ставший одним из самых популярных. В 1975 году Джон Соловай и Фолькер Штрассен опубликовали тест, основанный на символе Якоби. Развитие криптографии с открытым ключом в 1970-х годах дало мощный импульс исследованиям: потребовались быстрые методы генерации простых чисел длиной в сотни бит. Вероятностные тесты, такие как тест Ферма и тест Миллера — Рабина, стали стандартом де-факто в программном обеспечении (например, в библиотеках OpenSSL, GnuPG).

Принцип работы

Большинство вероятностных тестов основаны на проверке некоторого арифметического свойства, которое выполняется для всех простых чисел, но может выполняться и для некоторых составных. Если число \( n \) не удовлетворяет свойству, оно гарантированно составное (свидетель составности). Если же свойство выполняется, число объявляется «вероятно простым». Для повышения достоверности тест повторяют многократно с разными случайными параметрами (основаниями). Если после \( k \) раундов число каждый раз проходит проверку, вероятность того, что оно составное, не превышает \( 4^{-k} \) (для теста Миллера — Рабина).

Малая теорема Ферма

Малая теорема Ферма утверждает: если \( p \) — простое число, то для любого целого \( a \), не кратного \( p \), выполняется \( a^{p-1} \equiv 1 \pmod{p} \). Обратное неверно: существуют составные числа \( n \), для которых \( a^{n-1} \equiv 1 \pmod{n} \) для всех \( a \), взаимно простых с \( n \). Такие числа называются числами Кармайкла (например, 561). Тест Ферма, проверяющий это сравнение для одного или нескольких случайных \( a \), является простейшим вероятностным тестом, но уязвим для чисел Кармайкла.

Основные виды вероятностных тестов

Тест Ферма

Самый простой и быстрый тест. Выбирается случайное основание \( a \) (1 < a < n-1). Вычисляется \( a^{n-1} \mod n \). Если результат не равен 1, число составное. Если равен 1, число считается вероятно простым. Недостаток: числа Кармайкла проходят тест для всех \( a \), взаимно простых с \( n \), что делает тест ненадёжным для таких чисел.

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

Наиболее широко используемый вероятностный тест. Он основан на том, что для простого числа \( p \) уравнение \( x^2 \equiv 1 \pmod{p} \) имеет только два решения: \( x \equiv 1 \) и \( x \equiv -1 \). Для составного числа могут существовать и другие решения («нетривиальные квадратные корни из единицы»). Алгоритм:

1. Представить \( n-1 \) как \( d \cdot 2^s \), где \( d \) — нечётное.
2. Выбрать случайное основание \( a \) (1 < a < n-1).
3. Вычислить \( x = a^d \mod n \).
4. Если \( x \equiv 1 \) или \( x \equiv -1 \), тест пройден.
5. Повторять \( s-1 \) раз: \( x = x^2 \mod n \). Если на каком-то шаге \( x \equiv -1 \), тест пройден.
6. Если ни разу не встретилось \( \pm 1 \), число составное.

Вероятность ошибки для одного раунда не превышает 1/4. Для практических целей достаточно 10–20 раундов, чтобы вероятность ошибки стала пренебрежимо малой (менее \( 10^{-12} \)).

Тест Соловея — Штрассена

Основан на символе Якоби и свойстве: для простого нечётного \( p \) и любого \( a \), не кратного \( p \), выполняется \( a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \pmod{p} \), где \( \left(\frac{a}{p}\right) \) — символ Лежандра. Тест проверяет это сравнение для случайного \( a \). Вероятность ошибки для одного раунда не превышает 1/2. Тест менее эффективен, чем Миллера — Рабина, и реже используется на практике, хотя исторически был важным этапом.

Тест Люка — Лемера

Специализированный вероятностный тест для чисел Мерсенна (вида \( 2^p - 1 \)). Он является детерминированным для этого класса, но в общем случае не применяется. Для произвольных чисел существуют обобщения (тест Бейли — Померанса — Селфриджа, Уильямса), но они менее распространены.

Сравнение с детерминированными тестами

Детерминированные тесты (например, тест Адлемана — Померанса — Румели, тест Агравала — Каяла — Саксены, AKS) дают абсолютно точный ответ о простоте числа, но могут быть значительно медленнее для больших чисел (сотни и тысячи бит). AKS, опубликованный в 2002 году, имеет полиномиальную сложность, но на практике для чисел длиной в 1024 бита он работает в тысячи раз медленнее, чем тест Миллера — Рабина. Поэтому в криптографических приложениях почти всегда используются вероятностные тесты, а детерминированные — только для верификации или в научных исследованиях.

Применение

Основная область применения — криптография с открытым ключом. Для генерации ключей RSA необходимо найти два больших простых числа (обычно длиной 1024–4096 бит). Процесс выглядит так:

1. Случайным образом генерируется нечётное число нужной длины.
2. Применяется вероятностный тест (обычно Миллера — Рабина) с несколькими раундами.
3. Если число не проходит тест, оно отбрасывается, и генерируется новое.
4. Если число проходит, оно считается простым и используется.

Вероятность того, что составное число будет принято за простое, настолько мала (например, \( 2^{-80} \) при 40 раундах), что на практике считается нулевой. Кроме того, вероятностные тесты используются:

• В системах электронной подписи (DSA, ECDSA).
• В протоколах обмена ключами (Диффи — Хеллман).
• В алгоритмах факторизации (например, метод Полларда — p-1 требует проверки на простоту промежуточных чисел).
• В математическом программном обеспечении (Mathematica, Maple, PARI/GP) для быстрой проверки простоты.

Критика и ограничения

Основной недостаток — принципиальная неопределённость: результат «вероятно простое» не является строгим доказательством. Для некоторых приложений (например, в математических доказательствах) требуется абсолютная уверенность. В таких случаях применяются детерминированные тесты или сертификаты простоты (например, сертификат Пратта).

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

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

Интересные факты

• Наименьшее число, которое является сильным псевдопростым по основанию 2 для теста Миллера — Рабина — это 2047 (2047 = 23 × 89).
• Числа Кармайкла бесконечны (доказано в 1994 году), но их плотность среди чисел до \( N \) убывает как \( N^{1-o(1)} \).
• В 1980 году Майкл Рабин доказал, что вероятность ошибки теста Миллера — Рабина не превышает 1/4 для каждого раунда, что делает его одним из самых надёжных вероятностных тестов.
• Существует детерминированный вариант теста Миллера — Рабина, если верна расширенная гипотеза Римана: достаточно проверить все основания до \( 2(\ln n)^2 \). Однако гипотеза не доказана, поэтому на практике используют вероятностный вариант.

Источники

• Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы. — 3-е изд. — М.: Вильямс, 2007. — Глава 4.5.4.
• Rabin M. O. Probabilistic algorithm for testing primality // Journal of Number Theory. — 1980. — Vol. 12, no. 1. — P. 128–138.
• Solovay R., Strassen V. A fast Monte-Carlo test for primality // SIAM Journal on Computing. — 1977. — Vol. 6, no. 1. — P. 84–85.
• Crandall R., Pomerance C. Prime Numbers: A Computational Perspective. — 2nd ed. — Springer, 2005. — Глава 4.
• Малая теорема Ферма и числа Кармайкла: Carmichael R. D. On composite numbers \( P \) which satisfy the congruence \( a^{P-1} \equiv 1 \mod P \) // American Mathematical Monthly. — 1912. — Vol. 19, no. 2. — P. 22–27.