Как проверить число на простоту?

Степан Кузнецов
«Квант» №10, 2020

Как быстро проверить, является ли данное натуральное число n простым? Такая задача часто возникает на практике. Один из примеров — шифр RSA¹. Это асимметричный шифр: шифрование производится закрытым ключом (известен только отправителю), а расшифровка — открытым (известен всем). Чтобы сгенерировать такую пару ключей для шифра RSA, нужно выбрать два больших числа p и q, причем оба числа должны быть простыми — иначе шифр невозможно будет расшифровать.

Проще всего действовать по определению, перебирая все числа от 1 до n и проверяя, не является ли какое-то из них делителем. Этот способ можно немного усовершенствовать: если n = ab, то меньший из двух делителей a и b окажется меньше или равен \(\sqrt{n}\). Значит, достаточно перебирать числа не до n, а всего лишь до \(\sqrt{n}\).

Время работы такого алгоритма, однако, будет огромным. Например, если в двоичной записи числа n тысяча разрядов (это минимальная длина криптографического ключа RSA, гарантирующая безопасность), то число проверок равно \(\sqrt{n}\) ≈ 2⁵⁰⁰ ≈ 3 ⋅ 2¹⁵⁰. Если даже одна проверка делается за 1/10⁹ секунды (частота 1 гигагерц), то для выяснения простоты числа n понадобится 3 ⋅ 10¹⁴¹ c ≈ 10¹³⁴ лет! Можно попытаться «подобраться» к числу n с помощью решета Эратосфена, однако серьезного уменьшения времени работы это не даст. Нужны более глубокие идеи.

Начнем с малой теоремы Ферма (МТФ): если n — простое число, то для любого a от 1 до n − 1 число a^n − 1 при делении на n дает остаток 1 (т. е. a ^n − 1 ≡ 1(mod n)). Значит, если мы вдруг нашли такое a, что остаток оказался другим, то n заведомо не простое! Разумеется, перебирать все a в попытке найти нужное — затея не лучше, чем перебирать возможные делители. Но мы попробуем угадать a, выбирая его случайным образом.

Эта идея не такая безнадежная, как может показаться на первый взгляд. Действительно, пусть оказалось, что a₀^n − 1 \(\not≡\) 1(mod n), а a₁^n − 1 ≡ 1(mod n) (т. е. если мы выбрали a₀ , то мы угадали, а если выбрали a₁, то нет). Тогда (a₀ ⋅ a₁)^n − 1 ≡ a₀^n − 1 ⋅ a₁^n − 1 ≡ a₀^n − 1 \(\not≡\) 1(mod n) . Таким образом, если мы угадали с выбором a₀, то также удачным будет выбор a₀ ⋅ a₁. Более того, если a₀ взаимно просто с n, то для разных значений a₁ числа a₁ ⋅ a₂ будут различны по модулю n. Таким образом, среди всех чисел от 1 до n − 1, взаимно простых с n, окажется не менее половины «удачных»: действительно, каждому «неудачному» числу a₁ соответствует как минимум одно уникальное «удачное», равное остатку от деления a₀ ⋅ a₁ на n (где a₀ — одно фиксированное «удачное» число).

Итак, алгоритм — его называют тестом Ферма — действует так. Выбираем случайное a в диапазоне от 2 до n − 1 (число 1 выбирать бессмысленно). Если a не взаимно просто с n — это можно быстро проверить с помощью алгоритма Евклида² , то n заведомо составное. Иначе вычисляем остаток от деления a ^n − 1 на n, и если он не равен 1, то n — составное. Если же равен, то вероятность того, что мы выбрали «неудачное» a, а для другого a получился бы неединичный остаток, не превосходит 1/2. Возвести a в большую степень можно методом последовательного деления показателя пополам («быстрое возведение в степень»); при этом после каждого шага лучше брать остаток по модулю n, чтобы избежать слишком больших чисел. Повторяя алгоритм k раз, каждый раз выбирая случайное a независимо, мы уменьшим эту вероятность до 1/2^k , что очень быстро стремится к нулю с ростом k.

Подведем итог. Если тест Ферма отвечает, что n составное, то он совершенно точно прав; если говорит, что простое — то может ошибиться, но с очень малой вероятностью. Эту вероятность мы контролируем за счет изменения параметра k — например, можем сделать ее меньше, чем вероятность сбоя техники. Тогда на практике алгоритм будет неотличим от точного — а работает он намного быстрее, чем перебор делителей!

К сожалению, у теста Ферма есть фатальный недостаток. Существуют так называемые числа Кармайкла: эти вредные числа не являются простыми, но удовлетворяют МТФ для любого a, взаимно простого с n. В таком случае мы не сможем найти ни одного «удачного» a₀, и приведенное выше рассуждение недействительно. (Вероятность же случайно наткнуться на число a, не взаимно простое с n, мала.) Самые маленькие числа Кармайкла: 561, 1105, 1729. Числа Кармайкла относительно редки, однако, к сожалению, их бесконечно много³. (Иначе можно было бы «починить» тест Ферма, добавив в начале сверку с конечным списком чисел Кармайкла.)

Тем не менее, основную идею теста Ферма можно «спасти». Один из способов это сделать дает тест Соловея — Штрассена. Поскольку нас интересует случай нечетного n (иначе оно заведомо составное, если не равно 2), то n − 1 нацело делится на 2. Если n простое, то в силу МТФ имеем \(\left ( a^{\frac{n-1}{2}}-1 \right ) \left ( a^{\frac{n-1}{2}}+1 \right )=a^{n-1}-1\equiv0\pmod{n}\), откуда \(a^{\frac{n-1}{2}}\equiv\pm1\pmod{n}\). Более того, знак (+ или –) можно вычислить, зная a и n — это символ Якоби \(\left (\frac{a}{n} \right )\). Таким образом, мы получили новое сравнение, нарушение которого означает непростоту n, а именно: \(a^{\frac{n-1}{2}}\equiv\left ( \frac{a}{n} \right )\pmod{n}\). Теперь, однако, никакого аналога чисел Кармайкла нет: оказывается, что для составного n всегда найдется a₀, для которого \(a_0^{\frac{n-1}{2}}\not\equiv\left ( \frac{a}{n} \right )\pmod{n}\). Далее, как и для теста Ферма, можно доказать, что таких «удачных» a не менее половины среди всех чисел от 1 до n − 1, взаимно простых с n. Доказательства сформулированных выше фактов элементарные, но довольно технические. Их можно найти, например, в книге О. Н. Василенко «Теоретико-числовые алгоритмы в криптографии» (М.: МЦНМО, 2003).

Итак, получается алгоритм: выбираем случайное a от 2 до n − 1, взаимно простое с n (если нашлось не взаимно простое — немедленно отвечаем, что n составное); вычисляем остаток от деления \(a^{\frac{n-1}{2}}\) на n и сравниваем его по модулю n с \(\left ( \frac{a}{n} \right )\) . Если ответ «не равно», то a составное, иначе — предположительно простое. Во втором случае вероятность ошибки равна 1/2, теперь уже для любого n. Повторяя алгоритм k раз, снижаем вероятность ошибки до 1/2k .

Существуют и другие вероятностные тесты на простоту. А можно ли построить алгоритм проверки на простоту, который работает быстро и при этом выдает ответ точно, а не с некоторой (пусть и сколь угодно близкой к 1) вероятностью? Такие тесты называются детерминированными. Таков тест Миллера (1976). Этот тест быстрый и детерминированный, однако доказательство того, что он работает правильно, опирается на недоказанное утверждение — расширенную гипотезу Римана. Быстрый детерминированный тест, корректность которого доказана полностью, был предложен сравнительно недавно — это тест Агравала — Каяла — Саксены или AKS-тест (2002). Однако вероятностные тесты все еще работают быстрее, чем AKS-тест.

¹ Подробнее о шифре RSA читайте в статье В.А. Успенского «Как теория чисел помогает в шифровальном деле» (Соросовский образовательный журнал, 1996, №6).

² Вагутен В. Алгоритм Евклида и основная теорема арифметики («Квант», 1972, №6); Абрамов С. Самый знаменитый алгоритм («Квант», 1985, №11).

³ Alford W.R., Granville A., Pomerance C. There are infinitely many Carmichael numbers. Annals of Mathematics, 1994, vol. 139, p. 703–722.