Тесты Ферма и Миллера-Рабина на простоту

Салют хабровчане! Сегодня мы продолжаем делиться полезным материалом, перевод которого подготовлен специально для студентов курса «Алгоритмы для разработчиков».



Дано некоторое число n, как понять, что это число простое? Предположим, что n изначально нечетное, поскольку в противном случае задача совсем простая.

Самой очевидной идеей было бы искать все делители числа n, однако до сих пор основная проблема заключается в том, чтобы найти эффективный алгоритм.

---

Тест Ферма

По Теореме Ферма, если n – простое число, тогда для любого a справедливо следующее равенство an−1=1 (mod n). Отсюда мы можем вывести правило теста Ферма на проверку простоты числа: возьмем случайное a ∈ {1, ..., n−1} и проверим будет ли соблюдаться равенство an−1=1 (mod n). Если равенство не соблюдается, значит скорее всего n – составное.

Тем не менее, условие равенства может быть соблюдено, даже если n – не простое. Например, возьмем n = 561 = 3 × 11 × 17. Согласно Китайской теореме об остатках:

Z561 = Z3 × Z11 × Z17

, где каждое a ∈ Z^∗₅₆₁ отвечает следующему:

(x,y,z) ∈ Z∗3×Z∗1111×Z∗17.

По теореме Ферма, x2=1, y10=1, и z16=1. Поскольку 2, 10 и 16 все являются делителями 560, это значит, что (x,y,z)560 = (1, 1, 1), другими словами a560 = 1 для любого a ∈ Z∗561.

Не имеет значения какое a мы выберем, 561 всегда будет проходить тест Ферма несмотря на то, что оно составное, до тех пор, пока a является взаимно простым с n. Такие числа называются числами Кармайкла и оказывается, что их существует бесконечное множество.

Если a не взаимно простое с n, то оно тест Ферма не проходит, но в этом случае мы можем отказаться от тестов и продолжить искать делители n, вычисляя НОД(a,n).

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

Мы можем усовершенствовать тест, сказав, что n — простое тогда и только тогда, когда решениями x2 = 1 (mod n) являются x = ±1.

Таким образом, если n проходит тест Ферма, то есть an−1 = 1, тогда мы проверяем еще чтобы a(n−1)/2 = ±1, поскольку a(n−1)/2 это квадратный корень 1.

К сожалению, такие числа, как, например 1729 — третье число Кармайкла до сих пор могут обмануть этот улучшенный тест. Что если мы будем проводить итерации? То есть пока это будет возможно, мы будем уменьшать экспоненту вдвое, до тех пор, пока не дойдем до какого-либо числа, помимо 1. Если мы получим в итоге что-то, кроме -1, тогда n будет составным.

Если говорить более формально, то пускай 2^S будет самой большой степенью 2, делящейся на n-1, то есть n−1=2Sq для какого-то нечетного числа q. Каждое число из последовательности

an−1 = a(2^S)q, a(2^S-1)q,…, aq.

Это квадратный корень предшествующего члена последовательности.

Тогда если n – простое число, то последовательность должна начинаться с 1 и каждое последующее число тоже должно быть 1, или же первый член последовательность может быть не равен 1, но тогда он равен -1.

Тест Миллера-Рабина берет случайное a∈ Zn. Если вышеуказанная последовательность не начинается с 1, либо же первый член последовательности не равен 1 или -1, тогда n – не простое.

Оказывается, что для любого составного n, включая числа Кармайкла, вероятность пройти тест Миллера-Рабина равна примерно 1/4. (В среднем значительно меньше.) Таким образом, вероятность того, что n пройдет несколько прогонов теста, уменьшается экспоненциально.

Если n не проходит тест Миллера-Рабина с последовательностью начинающейся с 1, тогда у нас появляется нетривиальный квадратный корень из 1 по модулю n, и мы можем эффективно находить делители n. Поэтому числа Кармайкла всегда удобно раскладывать на множители.

Когда тест применяется к числам вида pq, где p и q – большие простые числа, они не проходят тест Миллера-Рабина практически во всех случаях, поскольку последовательность не начинается с 1. Итого, так мы RSA сломать не сможем.

На практике тест Миллера-Рабина реализуется следующим образом:

1. Дано n, нужно найти s, такое что n – 1 = 2Sq для некоторого нечетного q.
2. Возьмем случайное a ∈ {1,...,n−1}
3. Если a^q = 1, то n проходит тест и мы прекращаем выполнение.
4. Для i= 0, ... , s−1 проверить равенство a(2^i)q = −1. Если равенство выполняется, то n проходит тест (прекращаем выполнение).
5. Если ни одно из вышеприведенных условий не выполнено, то n – составное.

Перед выполнением теста Миллера-Рабина стоит провести еще несколько тривиальных делений на маленькие простые числа.

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

Существуют еще детерминированные алгоритма работающие за полиномиальное время для определения простоты (Agrawal, Kayal и Saxena), однако на сегодняшний день они считаются непрактичными.