Тест Миллера–Рабина: быстрая проверка простоты больших чисел
Как проверить простоту числа до 10¹⁸ за микросекунды: тест Ферма и его слабость, алгоритм Миллера–Рабина, детерминированные основания для 64 бит, код на Python и C++.
Коротко
| Способ | Сложность на одно число | Когда применять |
|---|---|---|
| Перебор делителей до √n | одно число до ~10¹² | |
| Решето Эратосфена | на все | все числа до ~10⁷–10⁸ |
| Тест Ферма | умножений | почти никогда: обманывается Кармайклом |
| Миллер–Рабин (случайный) | умножений | числа любого размера, ошибка ≤ |
| Миллер–Рабин (12 оснований) | умножений | любое 64-битное число, без ошибок |
Главная идея: по простому модулю у уравнения есть только корни . Если мы нашли «лишний» квадратный корень из единицы, число точно составное.
Зачем это нужно
Задача звучит просто: дано одно число n до , простое ли оно? Привычные инструменты здесь не работают.
Перебор до корня — это итераций. На Python это минуты, на C++ — около секунды на одно число. А если чисел тысяча?
Решето Эратосфена требует массив размером n. Для это не память, а фантастика. Решето хорошо, когда нужны все простые до разумной границы, — подробно о нём в статье про решето Эратосфена.
Нужен способ, который не ищет делитель, а проверяет какое-то свойство, присущее только простым числам. Причём быстро — за число операций, пропорциональное количеству цифр, а не самому числу.
Тест Ферма: идея и ловушка
Малая теорема Ферма: если p простое и a не делится на p, то
Отсюда наивный тест: возьмём случайное a, посчитаем pow(a, n - 1, n). Если результат не 1 — n точно составное. Возведение в степень по модулю делается за умножений, как описано в статье про быстрое возведение в степень.
import random def fermat_test(n: int, k: int = 10) -> bool: if n < 4: return n in (2, 3) for _ in range(k): a = random.randrange(2, n - 1) if pow(a, n - 1, n) != 1: return False # точно составное return True # «вероятно простое»
Проблема в обратном направлении. Если , число не обязательно простое. Например, , хотя . Такие n называют псевдопростыми по основанию a.
С отдельными псевдопростыми можно справиться, взяв несколько оснований. Но есть числа Кармайкла — составные n, для которых равенство выполняется при любом a, взаимно простом с n. Самое маленькое — :
print(pow(2, 560, 561)) # 1 print(pow(5, 560, 561)) # 1 print(pow(7, 560, 561)) # 1
Тест Ферма ловит 561 только тогда, когда случайно выбрал a, кратное 3, 11 или 17, — то есть фактически нашёл делитель. Для чисел Кармайкла с большими простыми множителями вероятность такого везения ничтожна, а самих чисел Кармайкла бесконечно много. Поэтому тест Ферма в чистом виде не используют.
Идея Миллера–Рабина
Миллер–Рабин усиливает Ферма одним наблюдением. Если p простое, то в арифметике по модулю p уравнение
имеет ровно два решения: и . Действительно, делится на простое p, только если на p делится один из множителей.
Для составного n бывают и другие корни. Для 561, например, , то есть , хотя 67 — это не ±1.
Теперь соединим это с Ферма. Число n нечётное, значит n − 1 чётное. Вынесем из него все двойки:
Тогда получается из последовательным возведением в квадрат s раз:
Если n простое, последний элемент равен 1 (Ферма). Каждый элемент — квадрат предыдущего. Значит, где-то в цепочке впервые появляется единица, и элемент перед ней — квадратный корень из 1, отличный от 1. По простому модулю это обязано быть .
Итого для простого n выполняется одно из двух:
- — цепочка сразу из единиц;
- какой-то элемент при равен .
Если не выполнено ни то, ни другое, основание a называют свидетелем составности, а n точно составное.
Разбор на примерах
n = 97 (простое). , то есть , . Берём :
| r | |
|---|---|
| 0 | 8 |
| 1 | 64 |
| 2 | 22 |
| 3 | 96 = −1 |
| 4 | 1 |
На шаге 3 появилось −1, дальше только единицы. Основание 2 не свидетель — тест пройден.
n = 561 (Кармайкл). , , . Снова :
| r | |
|---|---|
| 0 | 263 |
| 1 | 166 |
| 2 | 67 |
| 3 | 1 |
Единица появилась, но перед ней стоит 67, а не 560. Мы нашли нетривиальный корень из единицы — 561 составное. Ферма с тем же основанием сказал бы «простое».
Реализация
import random def is_witness(a: int, n: int, d: int, s: int) -> bool: """True, если основание a доказывает, что n составное.""" x = pow(a, d, n) if x == 1 or x == n - 1: return False for _ in range(s - 1): x = x * x % n if x == n - 1: return False return True def miller_rabin(n: int, k: int = 20) -> bool: if n < 4: return n in (2, 3) if n % 2 == 0: return False d, s = n - 1, 0 while d % 2 == 0: d //= 2 s += 1 for _ in range(k): a = random.randrange(2, n - 1) if is_witness(a, n, d, s): return False return True print(miller_rabin(561)) # False print(miller_rabin(2**61 - 1)) # True print(miller_rabin(10**18 + 9)) # True
Цикл внутри is_witness делает s − 1 возведений в квадрат, а не s: элемент проверять не нужно. Если до него не встретилось −1, то либо он не равен 1 (Ферма не выполняется), либо единице предшествует нетривиальный корень. Составное в обоих случаях.
Насколько можно доверять ответу
Ответ «составное» всегда верен — у нас на руках свидетель. Ответ «простое» вероятностный. Рабин доказал, что для любого нечётного составного n свидетелями являются не меньше трёх четвертей оснований. Значит, k случайных оснований ошибаются с вероятностью не больше . При это меньше , а на практике оценка сильно завышена.
В отличие от Ферма, для Миллера–Рабина не существует аналога чисел Кармайкла: никакое составное число не обманывает тест при всех основаниях.
Детерминированные наборы оснований
Для чисел ограниченного размера случайность не нужна. Перебором проверено, какие фиксированные наборы оснований не пропускают ни одного составного числа ниже заданной границы:
Граница n | Основания |
|---|---|
| 2 | |
| 2, 3, 5, 7 | |
| (> ) | 2, 7, 61 |
| (> ) | первые 12 простых: 2, 3, 5, …, 37 |
| 2, 325, 9375, 28178, 450775, 9780504, 1795265022 |
Границы точные: 2047 = 23 · 89 — первое число, которое проходит тест по основанию 2, а 3 215 031 751 = 151 · 751 · 28351 обманывает сразу основания 2, 3, 5 и 7 (основание 11 его ловит).
Для 64-битных чисел проще всего запомнить «первые 12 простых»:
BASES_64 = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) def is_prime(n: int) -> bool: """Детерминированно верно для всех n < 3.1 * 10**23.""" if n < 2: return False for p in BASES_64: if n % p == 0: return n == p d, s = n - 1, 0 while d % 2 == 0: d //= 2 s += 1 return not any(is_witness(a, n, d, s) for a in BASES_64) print(is_prime(3_215_031_751)) # False print(is_prime(2**64 - 59)) # True — наибольшее простое меньше 2^64
Пробное деление на сами основания решает две задачи сразу: быстро отсекает большинство составных и гарантирует, что a < n и a не кратно n.
Набор из семи оснований (найден Джимом Синклером) короче, но с ним есть тонкость: основания вроде 1795265022 могут быть больше n или кратны ему. Нужно брать a % n и пропускать нулевые основания, иначе тест объявит составными маленькие простые.
Я сверил обе версии с перебором для всех n < 200 000 и с независимой реализацией на 200 000 случайных 64-битных числах — расхождений нет.
Версия на C++: переполнение
В Python целые числа неограниченные, и x * x % n просто работает. В C++ для n около произведение двух остатков занимает до 128 бит, и uint64_t молча переполнится. Это самая частая ошибка в олимпиадных реализациях. Решение в GCC/Clang — unsigned __int128:
#include <cstdint> using u64 = uint64_t; using u128 = unsigned __int128; u64 power(u64 a, u64 e, u64 m) { u64 r = 1; a %= m; while (e) { if (e & 1) r = (u128)r * a % m; a = (u128)a * a % m; e >>= 1; } return r; } const u64 BASES[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}; bool is_prime(u64 n) { if (n < 2) return false; for (u64 p : BASES) if (n % p == 0) return n == p; u64 d = n - 1; int s = 0; while (d % 2 == 0) { d /= 2; ++s; } for (u64 a : BASES) { u64 x = power(a, d, n); if (x == 1 || x == n - 1) continue; bool composite = true; for (int i = 1; i < s && composite; ++i) { x = (u128)x * x % n; if (x == n - 1) composite = false; } if (composite) return false; } return true; }
Если , хватает uint64_t и оснований 2, 7, 61. В MSVC __int128 нет — там используют _umul128 или умножение Монтгомери.
Сложность
Одно основание — это одно возведение в степень по модулю, то есть умножений по модулю n. Для 64-битных чисел умножение константное, и вся проверка занимает , где k — число оснований (12 или 7). На практике это 12 · 64 ≈ 800 модульных умножений.
Для длинных чисел (сотни и тысячи бит) каждое умножение стоит при школьном алгоритме, итого .
Порядок величин на Python: проверка 64-битного простого — около 150 мкс, тогда как перебор до корня из занял бы минуты. В C++ — единицы микросекунд.
Сравнение подходов
| Ситуация | Что выбрать |
|---|---|
| Одно число до , собеседование | перебор до √n — проще и без ошибок |
| Много запросов, числа до | решето, ответ за |
| Числа до , олимпиада | детерминированный Миллер–Рабин |
| Числа в сотни бит (криптография) | Миллер–Рабин с многими основаниями или BPSW |
| Нужны делители, а не только «да/нет» | Миллер–Рабин + ро-Полларда |
Тест Ферма в таблице отсутствует намеренно: Миллер–Рабин стоит столько же, а ошибается гораздо реже.
В библиотеках Миллер–Рабин обычно комбинируют с тестом Люка. Такую связку называют BPSW (Baillie–PSW): для неё до сих пор не найдено ни одного контрпримера, хотя существование их не исключено. Например, sympy.isprime для больших чисел использует именно её, а BigInteger.isProbablePrime в Java — Миллер–Рабин плюс Люка.
Ро-Полларда: кратко
Миллер–Рабин отвечает «составное», но делитель не называет. Чтобы разложить 64-битное число, его комбинируют с ро-методом Полларда, который находит делитель примерно за . Сам метод подробно разобран в статье про разложение на простые множители, здесь — только как их склеить:
import math import random def pollard_rho(n: int) -> int: if n % 2 == 0: return 2 while True: c = random.randrange(1, n) x = y = random.randrange(2, n) d = 1 while d == 1: x = (x * x + c) % n y = (y * y + c) % n y = (y * y + c) % n d = math.gcd(x - y, n) if d != n: return d def factor(n: int, out: list[int] | None = None) -> list[int]: out = [] if out is None else out if n == 1: return out if is_prime(n): # без этой проверки ро-метод на простом зациклится out.append(n) return out d = pollard_rho(n) factor(d, out) factor(n // d, out) return out print(sorted(factor(2**64 - 1))) # [3, 5, 17, 257, 641, 65537, 6700417] print(sorted(factor(1_000_000_007 * 998_244_353))) # [998244353, 1000000007]
Здесь Миллер–Рабин играет роль условия остановки рекурсии: как только кусок оказался простым, дробить его дальше не нужно. Без быстрой проверки простоты ро-метод на простом n крутится бесконечно, потому что нетривиального делителя просто нет.
Типичные ошибки
Забыть малые случаи. n = 0, 1, 2, 3 и чётные числа нужно обработать до разложения n − 1. Иначе randrange(2, n - 1) упадёт, а для n = 2 получится и странное поведение.
Проверять только . Это тест Ферма, а не Миллер–Рабин. Вся сила алгоритма — в просмотре цепочки квадратов.
Сделать s квадратов вместо s − 1. Ошибки в ответе это не даст, но выдаёт непонимание, почему последний элемент проверять не нужно.
Основание, кратное n. С набором Синклера pow(a, d, n) для a % n == 0 даст 0, и простое число будет объявлено составным. Берите a % n и пропускайте ноль.
Переполнение в C++/Java. a * b % m для 64-битных a, b переполняется. Нужен __int128, Math.multiplyHigh или BigInteger.
Перепутать границы наборов. Основания 2, 7, 61 корректны только до 4 759 123 141. Для 64 бит их уже недостаточно.
Где встречается
На собеседованиях в продуктовые компании Миллер–Рабин почти не спрашивают: типичная задача «проверить, простое ли число» решается перебором до корня, а «посчитать простые до n» (Count Primes) — решетом. Миллер–Рабин всплывает как follow-up: «а если n до ?» Тогда достаточно рассказать идею: Ферма, проблема Кармайкла, цепочка квадратов и корни из единицы, детерминированный набор оснований.
В олимпиадном программировании это стандартный шаблон вместе с ро-Полларда. В криптографии — способ генерировать большие простые для RSA: берут случайное нечётное число нужной длины и проверяют его Миллером–Рабином, пока не повезёт. По теореме о распределении простых среди 1024-битных чисел примерно каждое 700-е простое, так что ждать недолго.
Что запомнить
- Тест Ферма проверяет и обманывается числами Кармайкла (561, 1105, 1729…).
- Миллер–Рабин раскладывает и ищет нетривиальный квадратный корень из 1 в цепочке
- «Составное» — всегда правда, «простое» с
kслучайными основаниями ошибается с вероятностью не больше . - Для первые 12 простых в качестве оснований дают точный ответ; до хватает 2, 7, 61.
- В C++ умножайте через
__int128. - Для факторизации больших чисел: Миллер–Рабин как проверка + ро-Полларда как поиск делителя.