Тест Миллера-Рабина: проверка простоты числа

Тест Миллера-Рабина помогает проверить, является ли большое целое число простым, не перебирая все возможные делители. Он исследует остатки степеней по модулю проверяемого числа. Если последовательность нарушает обязательное свойство простых чисел, составность установлена точно. Если проверка пройдена, число называют вероятно простым: оно ещё может оказаться составным. Попробуйте менять число и основание в калькуляторе: он показывает все остатки одного раунда и его результат.
Идея: искать свидетельство составности
Простое число имеет ровно два положительных делителя: единицу и само себя. Проверка делением до квадратного корня понятна, но для чисел с сотнями цифр перебор может быть слишком долгим. Миллер и Рабин используют необходимые свойства простых чисел, которые можно проверить модульными вычислениями.
Пусть нечётно. Выберем основание от до и построим цепочку остатков. Для простого она обязательно будет отвечать определённому правилу. Если правило нарушено, основание называют свидетелем составности. Оно доказывает, что составное, хотя конкретные множители при этом находить не обязательно.
Если правило выполняется, основание просто не смогло обнаружить составность. У составного числа могут быть такие основания: их называют сильными лжецами. Поэтому один успешный раунд и доказательство простоты - разные результаты. Для сравнения, теорема Вильсона даёт точный критерий простоты, но непосредственное вычисление факториала для больших чисел менее удобно.
Разложение и цепочка остатков
Сначала представим чётное число в виде
Вычислим , затем последовательно возведём остаток в квадрат:
Раунд пройден, если или хотя бы один остаток в цепочке равен . Иначе - свидетель составности. Условие про единицу относится именно к первому остатку: единица, появившаяся позднее без предшествующего , не делает раунд успешным.
На видео показана цепочка для и . Золотая точка последовательно проходит по остаткам; достижение означает, что этот раунд пройден.
Почему вообще возникает правило? По малой теореме Ферма для простого и допустимого основания выполняется . При этом по простому модулю из следует или . Поэтому при последовательном возведении в квадрат цепочка, которая завершается единицей, либо начинается с единицы, либо до неё встречает , то есть остаток . Это необходимое условие, но для отдельного основания оно не является достаточным.
Пример: число 21 и основание 2
Для имеем , то есть , . Берём и считаем:
- .
- .
- Начальный остаток не равен единице, а остатка в цепочке нет. Основание свидетельствует о составности.
Действительно, , но в самом тесте разложение на множители не требовалось. Обратите внимание: при в цепочке ровно два проверяемых остатка, и . Следующее возведение в квадрат не нужно для решения раунда.
Для контраста проверим по основанию : , а остатки равны . Последний равен , поэтому раунд пройден. Число 17 действительно простое, но из одного этого раунда данный факт ещё не следует.

Как читать результат одного раунда
Посмотрим на оба примера как на проверку необходимого условия. Для числа 21 в начале цепочки стоит 11, а не единица. Затем остаток 16 тоже не равен 20. Все разрешённые шаги исчерпаны, поэтому больше оснований для сомнения в выводе нет: число составное. Слова «вероятно» здесь не нужны. Свидетель может быть полезен даже тогда, когда делители неизвестны или слишком велики для ручного поиска.
Для числа 17 ситуация другая. Остаток 16 удовлетворяет условию, поэтому с выбранным основанием противоречия не возникло. Если бы вместо 17 встретилось составное число с таким же результатом раунда, пришлось бы выбрать другое основание, способное обнаружить проблему. Смысл нескольких раундов именно в том, чтобы дать проверке независимые возможности найти свидетельство.
Калькулятор ограничен небольшими нечётными числами для наглядности. Он выводит все остатки цепочки, даже если успешный результат получен раньше: это помогает увидеть дальнейшее поведение квадратов. Практическая реализация может остановить раунд сразу после первого достаточного условия. Изменяя основание, сравнивайте результат на одном и том же числе; изменяя число, следите, как меняются разложение и длина цепочки.
Порядок действий в алгоритме
Граничные случаи обрабатывают до построения цепочки: числа меньше двух не простые; и простые; остальные чётные числа составные. Для нечётного один раунд выглядит так:
- Разделите на степень двойки: получите и нечётное .
- Выберите целое основание в диапазоне от до .
- Вычислите . Если или , раунд пройден.
- Не более раз заменяйте на . При появлении раунд пройден.
- Если таких остатков нет, объявите составным. Иначе повторите раунд с новым основанием.
Если , шаг с повторными квадратами пропускается: достаточно проверить начальный остаток. Взаимная простота основания и заранее не обязательна. Если они имеют общий делитель больше единицы, допустимое основание всё равно обнаружит составность; отдельное вычисление наибольшего общего делителя иногда помогает сразу найти делитель.
Число возможных шагов зависит от того, сколько раз чётное число делится на два. Например, при получаем : здесь , поэтому после первого остатка дополнительных квадратов нет. При показатель равен четырём, и цепочка может содержать четыре остатка. Длина самой цепочки не говорит, простое ли число: важны именно полученные значения.
Возведение в степень выполняют быстрым алгоритмом: показатель записывают в двоичном виде, основание последовательно возводят в квадрат, а остаток берут после умножений. Так не нужно хранить огромное число целиком. Один раунд требует модульных умножений; их стоимость зависит от длины числа и используемой арифметики. В работе с большими числами важно применять целочисленный тип нужной точности, а не числа с плавающей точкой.
Что означает вероятность ошибки
Для любого фиксированного нечётного составного случайное равномерное основание из допустимого диапазона пропускает составность с вероятностью не более . Если каждый из раундов выбирает основание независимо и равномерно, вероятность того, что данное составное число пройдёт все раунды, не больше
Например, после пяти независимых раундов граница равна , или примерно . Это верхняя оценка вероятности пропустить заранее фиксированное составное число при описанном случайном выборе оснований. Она не означает автоматически, что вероятность составности числа после успешной проверки равна : для такого обратного вывода нужно знать, как выбирались сами кандидаты.
Повторение одного и того же основания не создаёт независимых испытаний. Если заранее взять фиксированный список оснований, оценку без дополнительных условий применять нельзя; детерминированные списки требуют отдельного доказательства для заданного диапазона чисел. В оригинальной статье Рабина подчёркнута односторонность ошибки: обнаруженная составность достоверна, а успешное прохождение может быть ошибочным.
Ложное прохождение и применение
Возьмём . Здесь , а . Поэтому основание пропускает это составное число уже на первом шаге. Оно не опровергает тест: алгоритм обещает лишь вероятность обнаружения при случайных основаниях, а не успех каждого основания.
Похожие идеи встречаются в символе Якоби и тесте Соловея–Штрассена: оба подхода используют арифметические свойства простых чисел и допускают одностороннюю вероятностную ошибку. При этом проверяемые свойства различаются. В алгоритме Рабина–Карпа остатки применяются для поиска подстроки, а не для проверки простоты. А в схеме Рабина простые числа нужны при построении ключей, но сама схема решает другую задачу - шифрование.
Тест полезен при поиске больших вероятно простых чисел, в том числе для криптографических алгоритмов. Реальные системы используют проверенные библиотеки, надёжный источник случайности и параметры выбранного стандарта; например, FIPS 186-5 NIST описывает процедуры проверки кандидатов и выбор числа раундов в своём контексте. Для строгого сертификата простоты одного вероятностного результата недостаточно: нужен метод, выдающий доказательство, или дополнительная проверка.
Частые ошибки
- Принимать каждый успешный раунд за доказательство. Составное число тоже может пройти проверку по отдельному основанию.
- Считать позднюю единицу успешным условием. Единица засчитывается в начале; затем ищут именно .
- Проверять неправильное число остатков. После выполняют не более квадратов, включая случай без дополнительных шагов.
- Применять оценку к повторённому основанию. Граница требует независимого равномерного выбора на каждом раунде.
- Смешивать вероятность ошибки с вероятностью простоты кандидата. Первая обусловлена фиксированным составным числом, вторая зависит и от способа выбора кандидатов.
FAQ
Можно ли сразу получить множители числа?
Не всегда. Свидетель доказывает составность, но тест не обязан возвращать делитель. Иногда наибольший общий делитель или нетривиальный квадратный корень единицы помогает его найти.
Чем тест отличается от проверки Ферма?
Проверка Ферма смотрит на сравнение . Миллер–Рабин дополнительно исследует промежуточные квадраты и может обнаружить составность даже тогда, когда сравнение Ферма выполняется.
Сколько раундов нужно?
Для учебной оценки выбирают по границе . Для практического применения число раундов и другие проверки берут из подходящего стандарта и реализации с учётом задачи и размера чисел.
Коротко
Тест Миллера-Рабина раскладывает на и проверяет цепочку остатков по модулю . Свидетель даёт точный ответ «составное»; пройденные раунды дают ответ «вероятно простое». При независимых равномерных основаниях вероятность пропустить фиксированное составное число за раундов не превосходит .
Читайте также

Постулат Бертрана: простое число между n и 2n
Постулат Бертрана гарантирует простое число между n и 2n. Разбираем строгие границы, примеры, следствия и идею доказательства через биномиальный коэффициент.

Постоянная Миллса: константа, печатающая простые
Постоянная Миллса A такая, что floor(A^3^n) всегда простое. Разбираем теорему Миллса 1947 года, первые миллсовы простые, значение константы и в чём подвох формулы.

Числа Серпинского: что это и накрывающий набор
Числа Серпинского простыми словами: что такое число Серпинского, почему 78557 наименьшее, как накрывающий набор простых делает k умножить 2 в степени n плюс 1 составным при любом n.

Гипотеза ABC: что такое rad и качество тройки
Гипотеза ABC простыми словами: формула rad(n), показатель качества q = log(c)/log(rad(abc)), примеры хороших ABC-троек и их связь с теоремой Ферма и IUT Мотидзуки.

Символ Лежандра: квадратичные вычеты по простому модулю
Символ Лежандра: определение через квадратичные вычеты по простому модулю, критерий Эйлера, мультипликативность, квадратичный закон взаимности Гаусса и быстрый алгоритм вычисления.

Теорема Вильсона: критерий простоты и факториал по модулю
Теорема Вильсона: формулировка , доказательство через спаривание обратных, обратное утверждение Лагранжа, обобщение Гаусса и почему это не практический тест простоты.