Тест Миллера - Рабина для проверки на простоту

Нужная теория

Возьмём любое простое число $p$. Пусть $p - 1 = 2^n \cdot m$, где $m$ — нечётно.

Утверждение:
Для любого числа $x$ выполнено:

Либо что $x^m \equiv 1 \pmod{p}$.
Либо что существует такое $k < n$, что $x^{2^k\cdot m} \equiv -1 \pmod{p}$.

Доказательство:
По малой теореме Ферма мы знаем, что $x^{p - 1} \equiv 1 \pmod{p}$. То есть $x^{2^n \cdot m} \equiv 1 \pmod{p}$. Заметим, что только $1$ и $-1$ в квадрате сравнимы с 1 по модулю $p$ (если есть $a$, что $a^2 \equiv 1 \pmod{p}$, то $a^2 - 1 \equiv 0 \pmod{p}$, а значит $(a - 1) \cdot (a + 1) \equiv 0 \pmod{p}$). А это значит, что либо $x^{2^{n - 1} \cdot m} \equiv 1 \pmod{p}$, либо $x^{2^{n - 1} \cdot m} \equiv -1 \pmod{p}$. В первом случае это значит, что либо $x^{2^{n - 2} \cdot m} \equiv 1 \pmod{p}$, либо $x^{2^{n - 2} \cdot m} \equiv -1 \pmod{p}$, и т.д.

Тогда заметим, что если есть какое-то число $x$, для которого не выполнено описанное утверждение, то значит $p$ точно не простое. Число $x$ называется свидетелем простоты числа $p$, если для него выполнено описанное выше утверждение (при этом $p$ в этом случае не обязательно простое).

Утверждение: (Теорема Рабина)
У составного числа $n$ не более $\varphi(n) / 4$ свидетелей простоты. ($\varphi(n)$ это функция Эйлера).

Доказательство:
Доказательство слишком сложное, возможно потом напишем его тут.

Так как $\varphi(n) < n$, то если взять случайное число $a$, то оно с вероятностью меньше $1/4$ будет свидетелем простоты числа $p$.

Алгоритм

Пусть есть число $p$, которое мы хотим проверить на простоту. Тогда проверка того, что $p - 1$ делится на $2$ работает за $O(\log p)$ (длина числа $p$). Так как максимальная степень 2, на которую делится $p - 1$ это $\log p$, то за $O(\log^2 p)$ можно представить $p - 1 = 2^n \cdot m$.

Далее можно взять случайное число $a$ от $1$ до $p$. С помощью быстрого возведения в степень можно посчитать $a^m$ по модулю $p$. Так как числа имеют длину $O(\log p)$, и умножение двух чисел работает за $O(\log^2 p)$, а значит быстрое возведение в степень работает за $O(\log^3 p)$. Так мы посчитали $a^m$ по модулю $p$. Если число сравнимо с -1 или 1, то $a$ — свидетель простоты. Если же нет, то $n$ раз возводим число в квадрат и проверяем, что не сравнимо ли оно с $-1$ по модулю $p$. Итого за $O(\log^3 n)$ можно проверить число на свидетеля простоты.

Дальше чем более точная вероятность того, что $p$ составное вам нужна, тем больше раз вам надо повторить тест. При этом если повторить тест $k$ раз и каждое число свидетель простоты, то число составное с вероятностью $1/2^{2k}$. Итого время работы $O(k\cdot\log^3 n)$.

Автор конспекта: Филипп Грибов

По всем вопросам пишите в telegram @grphil