EssayAI
Блог
Блог
Математика и алгоритмы

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

8 ноября 2026Время чтения: 9 минут
#тест миллера-рабина#простые числа#теория чисел#алгоритмы#вероятность ошибки
Тест Миллера-Рабина: проверка простоты числа

Тест Миллера-Рабина помогает проверить, является ли большое целое число простым, не перебирая все возможные делители. Он исследует остатки степеней по модулю проверяемого числа. Если последовательность нарушает обязательное свойство простых чисел, составность установлена точно. Если проверка пройдена, число называют вероятно простым: оно ещё может оказаться составным. Попробуйте менять число и основание в калькуляторе: он показывает все остатки одного раунда и его результат.

Идея: искать свидетельство составности

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

Пусть n>3n > 3 нечётно. Выберем основание aa от 22 до n−2n-2 и построим цепочку остатков. Для простого nn она обязательно будет отвечать определённому правилу. Если правило нарушено, основание aa называют свидетелем составности. Оно доказывает, что nn составное, хотя конкретные множители при этом находить не обязательно.

Если правило выполняется, основание просто не смогло обнаружить составность. У составного числа могут быть такие основания: их называют сильными лжецами. Поэтому один успешный раунд и доказательство простоты - разные результаты. Для сравнения, теорема Вильсона даёт точный критерий простоты, но непосредственное вычисление факториала для больших чисел менее удобно.

Разложение и цепочка остатков

Сначала представим чётное число n−1n-1 в виде

n−1=2sd,d нечётно,s≥1.n-1 = 2^s d, \qquad d \text{ нечётно}, \quad s \geq 1.

Вычислим x0=ad mod nx_0 = a^d \bmod n, затем последовательно возведём остаток в квадрат:

x1=x02 mod n,x2=x12 mod n,…,xs−1=xs−22 mod n.x_1 = x_0^2 \bmod n, \quad x_2 = x_1^2 \bmod n, \quad \ldots, \quad x_{s-1} = x_{s-2}^2 \bmod n.

Раунд пройден, если x0=1x_0=1 или хотя бы один остаток в цепочке равен n−1n-1. Иначе aa - свидетель составности. Условие про единицу относится именно к первому остатку: единица, появившаяся позднее без предшествующего n−1n-1, не делает раунд успешным.

На видео показана цепочка для n=17n=17 и a=3a=3. Золотая точка последовательно проходит по остаткам; достижение 16=n−116=n-1 означает, что этот раунд пройден.

Для числа 17 и основания 3 точка проходит по остаткам 3, 9, 13 и 16, последовательно полученным возведением в квадрат по модулю 17.

Почему вообще возникает правило? По малой теореме Ферма для простого nn и допустимого основания aa выполняется an−1≡1(modn)a^{n-1} \equiv 1 \pmod n. При этом по простому модулю из x2≡1x^2 \equiv 1 следует x≡1x \equiv 1 или x≡−1x \equiv -1. Поэтому при последовательном возведении в квадрат цепочка, которая завершается единицей, либо начинается с единицы, либо до неё встречает −1-1, то есть остаток n−1n-1. Это необходимое условие, но для отдельного основания оно не является достаточным.

Пример: число 21 и основание 2

Для n=21n=21 имеем 20=22⋅520=2^2\cdot5, то есть s=2s=2, d=5d=5. Берём a=2a=2 и считаем:

  1. x0=25 mod 21=32 mod 21=11x_0=2^5 \bmod 21=32 \bmod 21=11.
  2. x1=112 mod 21=121 mod 21=16x_1=11^2 \bmod 21=121 \bmod 21=16.
  3. Начальный остаток не равен единице, а остатка 2020 в цепочке нет. Основание 22 свидетельствует о составности.

Действительно, 21=3⋅721=3\cdot7, но в самом тесте разложение на множители не требовалось. Обратите внимание: при s=2s=2 в цепочке ровно два проверяемых остатка, x0x_0 и x1x_1. Следующее возведение в квадрат не нужно для решения раунда.

Для контраста проверим 1717 по основанию 33: 16=24⋅116=2^4\cdot1, а остатки равны 3,9,13,163,9,13,16. Последний равен 17−117-1, поэтому раунд пройден. Число 17 действительно простое, но из одного этого раунда данный факт ещё не следует.

Сравнение цепочек: для 21 получены 11 и 16, для 17 - 3, 9, 13 и 16
Сравнение цепочек: для 21 получены 11 и 16, для 17 - 3, 9, 13 и 16

Как читать результат одного раунда

Посмотрим на оба примера как на проверку необходимого условия. Для числа 21 в начале цепочки стоит 11, а не единица. Затем остаток 16 тоже не равен 20. Все разрешённые шаги исчерпаны, поэтому больше оснований для сомнения в выводе нет: число составное. Слова «вероятно» здесь не нужны. Свидетель может быть полезен даже тогда, когда делители неизвестны или слишком велики для ручного поиска.

Для числа 17 ситуация другая. Остаток 16 удовлетворяет условию, поэтому с выбранным основанием противоречия не возникло. Если бы вместо 17 встретилось составное число с таким же результатом раунда, пришлось бы выбрать другое основание, способное обнаружить проблему. Смысл нескольких раундов именно в том, чтобы дать проверке независимые возможности найти свидетельство.

Калькулятор ограничен небольшими нечётными числами для наглядности. Он выводит все остатки цепочки, даже если успешный результат получен раньше: это помогает увидеть дальнейшее поведение квадратов. Практическая реализация может остановить раунд сразу после первого достаточного условия. Изменяя основание, сравнивайте результат на одном и том же числе; изменяя число, следите, как меняются разложение и длина цепочки.

Порядок действий в алгоритме

Граничные случаи обрабатывают до построения цепочки: числа меньше двух не простые; 22 и 33 простые; остальные чётные числа составные. Для нечётного n>3n>3 один раунд выглядит так:

  1. Разделите n−1n-1 на степень двойки: получите ss и нечётное dd.
  2. Выберите целое основание aa в диапазоне от 22 до n−2n-2.
  3. Вычислите x=ad mod nx=a^d\bmod n. Если x=1x=1 или x=n−1x=n-1, раунд пройден.
  4. Не более s−1s-1 раз заменяйте xx на x2 mod nx^2\bmod n. При появлении n−1n-1 раунд пройден.
  5. Если таких остатков нет, объявите nn составным. Иначе повторите раунд с новым основанием.

Если s=1s=1, шаг с повторными квадратами пропускается: достаточно проверить начальный остаток. Взаимная простота основания и nn заранее не обязательна. Если они имеют общий делитель больше единицы, допустимое основание всё равно обнаружит составность; отдельное вычисление наибольшего общего делителя иногда помогает сразу найти делитель.

Число возможных шагов зависит от того, сколько раз чётное число n−1n-1 делится на два. Например, при n=7n=7 получаем 6=2⋅36=2\cdot3: здесь s=1s=1, поэтому после первого остатка дополнительных квадратов нет. При n=17n=17 показатель равен четырём, и цепочка может содержать четыре остатка. Длина самой цепочки не говорит, простое ли число: важны именно полученные значения.

Возведение в степень выполняют быстрым алгоритмом: показатель записывают в двоичном виде, основание последовательно возводят в квадрат, а остаток берут после умножений. Так не нужно хранить огромное число ada^d целиком. Один раунд требует O(log⁡n)O(\log n) модульных умножений; их стоимость зависит от длины числа и используемой арифметики. В работе с большими числами важно применять целочисленный тип нужной точности, а не числа с плавающей точкой.

Что означает вероятность ошибки

Для любого фиксированного нечётного составного nn случайное равномерное основание из допустимого диапазона пропускает составность с вероятностью не более 1/41/4. Если каждый из kk раундов выбирает основание независимо и равномерно, вероятность того, что данное составное число пройдёт все раунды, не больше

(14)k=4−k.\left(\frac14\right)^k = 4^{-k}.

Например, после пяти независимых раундов граница равна 1/10241/1024, или примерно 0,098%0{,}098\%. Это верхняя оценка вероятности пропустить заранее фиксированное составное число при описанном случайном выборе оснований. Она не означает автоматически, что вероятность составности числа после успешной проверки равна 1/10241/1024: для такого обратного вывода нужно знать, как выбирались сами кандидаты.

Повторение одного и того же основания не создаёт независимых испытаний. Если заранее взять фиксированный список оснований, оценку 4−k4^{-k} без дополнительных условий применять нельзя; детерминированные списки требуют отдельного доказательства для заданного диапазона чисел. В оригинальной статье Рабина подчёркнута односторонность ошибки: обнаруженная составность достоверна, а успешное прохождение может быть ошибочным.

Ложное прохождение и применение

Возьмём 2047=23⋅892047=23\cdot89. Здесь 2046=2⋅10232046=2\cdot1023, а 21023 mod 2047=12^{1023}\bmod2047=1. Поэтому основание 22 пропускает это составное число уже на первом шаге. Оно не опровергает тест: алгоритм обещает лишь вероятность обнаружения при случайных основаниях, а не успех каждого основания.

Похожие идеи встречаются в символе Якоби и тесте Соловея–Штрассена: оба подхода используют арифметические свойства простых чисел и допускают одностороннюю вероятностную ошибку. При этом проверяемые свойства различаются. В алгоритме Рабина–Карпа остатки применяются для поиска подстроки, а не для проверки простоты. А в схеме Рабина простые числа нужны при построении ключей, но сама схема решает другую задачу - шифрование.

Тест полезен при поиске больших вероятно простых чисел, в том числе для криптографических алгоритмов. Реальные системы используют проверенные библиотеки, надёжный источник случайности и параметры выбранного стандарта; например, FIPS 186-5 NIST описывает процедуры проверки кандидатов и выбор числа раундов в своём контексте. Для строгого сертификата простоты одного вероятностного результата недостаточно: нужен метод, выдающий доказательство, или дополнительная проверка.

Частые ошибки

  • Принимать каждый успешный раунд за доказательство. Составное число тоже может пройти проверку по отдельному основанию.
  • Считать позднюю единицу успешным условием. Единица засчитывается в начале; затем ищут именно n−1n-1.
  • Проверять неправильное число остатков. После x0x_0 выполняют не более s−1s-1 квадратов, включая случай s=1s=1 без дополнительных шагов.
  • Применять оценку к повторённому основанию. Граница 4−k4^{-k} требует независимого равномерного выбора на каждом раунде.
  • Смешивать вероятность ошибки с вероятностью простоты кандидата. Первая обусловлена фиксированным составным числом, вторая зависит и от способа выбора кандидатов.

FAQ

Можно ли сразу получить множители числа?

Не всегда. Свидетель доказывает составность, но тест не обязан возвращать делитель. Иногда наибольший общий делитель или нетривиальный квадратный корень единицы помогает его найти.

Чем тест отличается от проверки Ферма?

Проверка Ферма смотрит на сравнение an−1≡1(modn)a^{n-1}\equiv1\pmod n. Миллер–Рабин дополнительно исследует промежуточные квадраты и может обнаружить составность даже тогда, когда сравнение Ферма выполняется.

Сколько раундов нужно?

Для учебной оценки выбирают kk по границе 4−k4^{-k}. Для практического применения число раундов и другие проверки берут из подходящего стандарта и реализации с учётом задачи и размера чисел.

Коротко

Тест Миллера-Рабина раскладывает n−1n-1 на 2sd2^s d и проверяет цепочку остатков ad,a2d,…a^d, a^{2d},\ldots по модулю nn. Свидетель даёт точный ответ «составное»; пройденные раунды дают ответ «вероятно простое». При независимых равномерных основаниях вероятность пропустить фиксированное составное число за kk раундов не превосходит 4−k4^{-k}.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Постулат Бертрана: простое число между n и 2n

Постулат Бертрана: простое число между n и 2n

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

8 ноября 20268 минут
Постоянная Миллса: константа, печатающая простые

Постоянная Миллса: константа, печатающая простые

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

19 июня 20267 минут
Числа Серпинского: что это и накрывающий набор

Числа Серпинского: что это и накрывающий набор

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

11 июня 20268 минут
Гипотеза ABC: что такое rad и качество тройки

Гипотеза ABC: что такое rad и качество тройки

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

11 июня 20268 минут
Символ Лежандра: квадратичные вычеты по простому модулю

Символ Лежандра: квадратичные вычеты по простому модулю

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

20 февраля 202611 минут
Теорема Вильсона: критерий простоты и факториал по модулю

Теорема Вильсона: критерий простоты и факториал по модулю

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

20 февраля 20268 минут