Математика / Арифметика и теория чисел

Быстрое возведение в степень по модулю двоичным методом

Двоичный метод вычисляет остаток большой степени, многократно возводя основание в квадрат и используя биты показателя. После каждого умножения можно брать остаток, не создавая огромного целого aⁿ.

Опубликовано: 21 октября 2026 г.Обновлено: 21 октября 2026 г.

Теория чисел Алгебра Страницы с задачами и решениями Есть историческая справка

Формула

a^n\bmod m,\qquad a^{2q}=(a^q)^2,\quad a^{2q+1}=a(a^q)^2

Схема Квадраты основания для 7¹³ mod 20

13 = 8 + 4 + 1; остаток 1 · 1 · 7 = 7

Обозначения

$a$: целое основание степени, безразмерное целое
$n$: неотрицательный целый показатель, безразмерное целое
$m$: положительный целый модуль, безразмерное целое
$r,b,e$: накопленный остаток, текущее основание и оставшийся показатель, целые числа

Условия применения

Основание целое, показатель n ≥ 0, модуль m > 0. Начальные значения r = 1 mod m, b = a mod m, e = n. Взаимная простота a и m не требуется. При n = 0 получается 1 mod m; в том числе при m = 1 ответ равен нулю. Отрицательный показатель требует отдельного вычисления обратного элемента.

Ограничения

Оценка O(log n) относится к числу модульных умножений, а не к полной битовой стоимости больших чисел. Произведение двух остатков может переполнить фиксированный тип до взятия модуля. Простой учебный цикл не обеспечивает защиту от побочных каналов и не должен автоматически считаться криптографической реализацией.

Подробное объяснение

Показатель записывается в двоичной системе как сумма степеней двойки. Поэтому aⁿ можно собрать из a, a², a⁴, a⁸ и следующих квадратов, выбирая только те множители, которым соответствуют единичные биты. Вместо n последовательных умножений нужно число шагов порядка длины двоичной записи n.

В правостороннем варианте хранят r, b и e. Если e нечётно, умножают r на b и берут остаток. Затем b заменяют его квадратом по модулю, а e — целой частью e/2. Этот переход удаляет младший бит, не меняя итоговый искомый остаток.

Корректность удобно проверять инвариантом r·bᵉ ≡ aⁿ по модулю m. Для чётного e квадрат основания и деление показателя пополам сохраняют произведение. Для нечётного один множитель b сначала переносится в r. При e = 0 остаётся только r, которое и является ответом.

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

Алгоритм не сокращает показатель по p−1 или φ(m) и не нуждается в простоте модуля. Это отличает его от теорем о периодичности. Такие теоремы иногда дополнительно уменьшают показатель, но только после проверки своих условий; двоичный цикл можно применять без этого шага.

Как пользоваться формулой

Проверьте n ≥ 0 и m > 0; приведите основание к остатку, задайте r = 1 mod m и сохраните исходные данные.
Если оставшийся показатель нечётный, умножьте накопленный остаток на текущее основание и возьмите остаток по m.
Возведите текущее основание в квадрат по модулю и замените показатель целой частью его половины; повторяйте до нуля.
Проверьте остаток прямым вычислением для малого случая или другим разложением показателя и контролируйте переполнение произведений.

Историческая справка

Повторное возведение в квадрат относится к алгоритмической традиции вычисления степеней через короткую цепочку промежуточных результатов. В современной теории чисел двоичная запись показателя делает эту цепочку систематической и даёт простой инвариант для доказательства программы. Учебные разделы о сравнениях связывают процедуру с сохранением остатка при умножении; теоремы Ферма и Эйлера объясняют отдельные возможности уменьшения показателя. Исторически эти математические результаты и современная программная реализация относятся к разным уровням: теоремы о степенях развивались в XVII–XVIII веках, а стоимость машинных операций и переполнение требуют уже вычислительного анализа. Единственный автор показанного учебного цикла по используемым источникам не устанавливается.

Историческая линия формулы

Двоичное возведение в степень — описательное название алгоритма повторного возведения в квадрат. Его корректность следует из разложения показателя и свойств сравнений. Имена Ферма и Эйлера относятся к связанным теоремам о степенях, но не используются для персонального авторства этого цикла.

Пример

Вычислим 7¹³ mod 20. Начинаем с r = 1, b = 7, e = 13. Показатель нечётен: r = 7. После квадрата b = 49 mod 20 = 9, e = 6. При чётном e накопитель не меняется; квадрат даёт b = 81 mod 20 = 1, e = 3. Теперь r = 7·1 mod 20 = 7, следующий квадрат оставляет b = 1, e = 1. Последний единичный бит снова даёт r = 7; после деления e = 0. Ответ 7. Независимая проверка использует 7⁴ ≡ 1 mod 20 и разложение 13 = 3·4+1: остаток также равен 7. Взаимная простота в работе цикла не использовалась. Все операции целочисленные; округлений и физических единиц здесь нет.

Частая ошибка

Не используйте обычное деление показателя вместо целочисленного. Не забывайте накопитель при единичном бите. Не вычисляйте степень с плавающей точкой ради остатка. Не объявляйте метод неприменимым при составном модуле. Не берите остаток только после переполненного умножения: уже потерянные биты восстановить нельзя.

Практика

Задачи с решением

Непростой модуль

Условие. Вычислите 6⁵ mod 8.

Решение. 6² ≡ 4, 6⁴ ≡ 4² ≡ 0 mod 8. Поэтому 6⁵ ≡ 0·6 ≡ 0. Общий делитель основания и модуля не мешает двоичному методу.

Ответ. 0.

Разложение показателя

Условие. Найдите 5²³ mod 17 через 23 = 16+4+2+1.

Решение. 5² ≡ 8, 5⁴ ≡ 13, 5⁸ ≡ 16, 5¹⁶ ≡ 1. Произведение 1·13·8·5 = 520 даёт остаток 10 по модулю 17.

Ответ. 10.

Дополнительные источники

https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Yet_Another_Introductory_Number_Theory_Textbook_-_Cryptology_Emphasis_%28Poritz%29/03%3A_Primes_Numbers/3.04%3A_Another_Approach_to_Fermat%27s_Little_and_Euler%27s_Theorems
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/An_Introduction_to_the_Theory_of_Numbers_%28Moser%29/01%3A_Chapters/1.05%3A_Congruences

Связанные формулы

Математика

Малая теорема Ферма: степени по простому модулю

$a^{p-1}\equiv1\pmod p,\quad p\text{ простое},\quad p\nmid a$

Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.

Математика

Теорема Эйлера: сокращение степени по составному модулю

$a^{\varphi(m)}\equiv1\pmod m,\qquad \gcd(a,m)=1,\quad m>1$

Теорема Эйлера даёт единичный остаток для основания, взаимно простого с модулем, в степени φ(m). Она работает и с составным модулем, но не позволяет без проверки сокращать показатель любого основания.

Математика

Линейное сравнение: решения через НОД коэффициента и модуля

$ax\equiv b\pmod m\text{ разрешимо}\iff d\mid b,\quad d=\gcd(a,m);\quad x=x_0+k\frac md,\ k=0,\ldots,d-1$

Сравнение ax ≡ b по модулю m имеет решения тогда и только тогда, когда НОД(a,m) делит b. При выполнении условия получается ровно d разных классов по исходному модулю, где d — этот НОД.

Математика

Мультипликативный порядок: минимальный период степеней

$\operatorname{ord}_m(a)=\min\{k\ge1:a^k\equiv1\pmod m\},\qquad\operatorname{ord}_m(a)\mid\varphi(m)$

Мультипликативный порядок обратимого остатка — наименьшая положительная степень, в которой он возвращается к единице. Этот период делит φ(m) и позволяет сокращать показатели точнее, чем одна теорема Эйлера.