Как быстро возвести в степень: бинарный алгоритм

Дано: основание $a = 7$, показатель $n = 93$, модуль $m = 101$. Найти: остаток $7^{93} \bmod 101$ и число умножений, которое на это уйдёт.

Считать сам $7^{93}$ не нужно: показатель раскладывается в двоичную запись $93 = 1011101_2$, основание последовательно возводится в квадрат по модулю, и потом перемножаются только нужные квадраты. Ответ: $7^{93} \equiv 55 \pmod{101}$, и получен он за 10 умножений вместо 92. Калькулятор сверху проходит ту же лестницу для любых $a$, $n$ и $m$, а ниже разбор по шагам.

Решение по шагам

Дано. $a = 7$, $n = 93$, $m = 101$. Найти: $7^{93} \bmod 101$.

Шаг 1. Раскладываем показатель в двоичную запись. Делим 93 на 2 с остатком, пока не дойдём до нуля, и читаем остатки снизу вверх:

$$93 = 64 + 16 + 8 + 4 + 1 = 1011101_2.$$

Единицы стоят на местах $2^0$, $2^2$, $2^3$, $2^4$ и $2^6$, поэтому исходная степень распадается в произведение пяти множителей:

$$7^{93} = 7^{64} \cdot 7^{16} \cdot 7^{8} \cdot 7^{4} \cdot 7^{1}.$$

Шаг 2. Строим таблицу последовательных квадратов. Каждая строка получается возведением предыдущей в квадрат, и остаток берётся сразу же, поэтому числа никогда не выходят за пределы $101^2$:

Шести умножений хватило, чтобы получить $7^{64} \equiv 81 \pmod{101}$, хотя в самом числе $7^{64}$ больше полусотни цифр.

Шаг 3. Перемножаем отмеченные строки. Нужны $k = 0, 2, 3, 4, 6$, то есть остатки 7, 78, 24, 71 и 81. Умножаем по очереди и после каждого умножения сразу приводим по модулю:

$$\begin{aligned} 7 \cdot 78 &= 546 = 5 \cdot 101 + 41 &&\equiv 41, \\ 41 \cdot 24 &= 984 = 9 \cdot 101 + 75 &&\equiv 75, \\ 75 \cdot 71 &= 5325 = 52 \cdot 101 + 73 &&\equiv 73, \\ 73 \cdot 81 &= 5913 = 58 \cdot 101 + 55 &&\equiv 55. \end{aligned}$$

Шаг 4. Считаем цену вычисления. Шесть возведений в квадрат в таблице плюс четыре умножения при сборке дают десять операций. Наивное перемножение семёрки на себя потребовало бы 92 умножения, то есть в 9,2 раза больше, а для показателя в тысячу разрыв стал бы стократным.

Ответ: $7^{93} \equiv 55 \pmod{101}$, вычислено за 10 умножений вместо 92.

Формула: почему показатель можно удваивать

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

$$a^{2k} = \left(a^{k}\right)^{2}, \qquad a^{2k+1} = \left(a^{k}\right)^{2} \cdot a.$$

Чётный показатель стоит ровно одного возведения в квадрат, нечётный обходится в квадрат плюс одно домножение на основание. За один шаг показатель уменьшается вдвое, поэтому шагов будет столько, сколько цифр в двоичной записи $n$, а не столько, сколько единиц в самом $n$.

Второе, что делает счёт возможным, - свойство сравнений: остаток произведения зависит только от остатков сомножителей,

$$(x \cdot y) \bmod m = \left((x \bmod m) \cdot (y \bmod m)\right) \bmod m.$$

Отсюда правило, которое экономит не время, а разрядность: приводить по модулю нужно после каждого умножения, а не в конце. Тогда любое промежуточное произведение меньше $m^2$ и помещается в обычный целый тип, тогда как честный $7^{93}$ занимает 79 десятичных цифр.

Общее число умножений считается по двоичной записи точно:

$$N(n) = \lfloor \log_2 n \rfloor + s(n) - 1,$$

где $s(n)$ - количество единиц. Для $n = 93$ получаем $6 + 5 - 1 = 10$, что и вышло в разборе. В худшем случае, когда все биты единичные, оценка равна $2\lfloor \log_2 n \rfloor$, в лучшем (степень двойки) - просто $\lfloor \log_2 n \rfloor$. Обе оценки логарифмические: показателю в миллион нужно около тридцати умножений.

Второй способ: лестница слева направо

Таблицу квадратов можно не хранить. Заведём один остаток $r = 1$ и пройдём двоичную запись показателя от старшего бита к младшему: на каждом бите возводим $r$ в квадрат, а если бит равен единице, дополнительно умножаем на основание. Показатель при этом собирается по схеме Горнера: удваивается и иногда получает плюс единицу.

Последний столбец совпал с ответом первого способа, и число умножений то же самое: шесть квадрирований и четыре домножения. Разница только в памяти: способ справа налево держит таблицу из $\lfloor \log_2 n \rfloor + 1$ значений, способ слева направо - одно число. Именно поэтому в библиотеках длинной арифметики реализован обычно второй вариант, а на бумаге удобнее первый: таблица квадратов наглядна и её легко проверить.

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

Проверка ответа малой теоремой Ферма

Модуль 101 простой, а основание 7 на него не делится, поэтому работает малая теорема Ферма: $7^{100} \equiv 1 \pmod{101}$. Показателю 93 не хватает до сотни ровно семёрки, значит $7^{93} \cdot 7^{7} \equiv 1 \pmod{101}$, и найденный остаток обязан быть обратным к $7^7$.

Считаем правую часть отдельно: $7^{7} = 7^{4} \cdot 7^{2} \cdot 7 \equiv 78 \cdot 49 \cdot 7 \equiv 90 \pmod{101}$. Проверяем произведение: $55 \cdot 90 = 4950 = 49 \cdot 101 + 1 \equiv 1$. Сошлось, ответ верен.

Та же теорема даёт полезный приём для огромных показателей: если $\gcd(a, m) = 1$, показатель заранее сокращается по модулю $\varphi(m)$, а для простого $m$ - по модулю $m - 1$. Например, $7^{2026} \bmod 101$ сводится к $7^{26} \bmod 101$, потому что $2026 = 20 \cdot 100 + 26$, и бинарный алгоритм после такого сокращения работает с показателем из пяти бит вместо одиннадцати. Проверять взаимную простоту обязательно: при $\gcd(a, m) \neq 1$ сокращение показателя неверно.

Где это считают: большие модули и степени матриц

Возведение в степень по модулю - рабочая операция асимметричной криптографии, и без бинарного алгоритма она была бы невыполнима: показатель там имеет порядок $2^{2048}$, а бинарный способ укладывается примерно в три тысячи умножений. На этой операции построены обмен ключами Диффи-Хеллмана и схема Эль-Гамаля; модульная арифметика в том же виде, только над матрицами, лежит в основе шифра Хилла.

Алгоритм не привязан к числам: он работает в любой структуре с ассоциативным умножением. Для матриц это даёт быстрое вычисление $P^n$ - например, при поиске распределения цепи Маркова через матрицу переходов или при вычислении $n$-го числа Фибоначчи за логарифмическое время через степень матрицы $2 \times 2$.

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

• Сначала считают степень, потом берут остаток. Число $7^{93}$ имеет 79 цифр, а при криптографических размерах не поместится в память вообще. Приводить по модулю нужно после каждого умножения.
• Пропускают приведение внутри таблицы квадратов. Если возводить в квадрат уже приведённый остаток, произведение не превысит $m^2$; если тянуть полное число, разрядность удваивается на каждой строке.
• Теряют или добавляют бит. Число сомножителей в сборке равно числу единиц: для 93 их пять. Быстрая проверка - сумма выбранных степеней двойки должна дать сам показатель: $64 + 16 + 8 + 4 + 1 = 93$.
• Перемножают показатели вместо сложения. При сборке $7^{64} \cdot 7^{16} = 7^{80}$, а не $7^{1024}$: показатели складываются, это и есть смысл двоичного разложения.
• Сокращают показатель по модулю $m$, а не по $\varphi(m)$. Правильно $7^{2026} \equiv 7^{26} \pmod{101}$, потому что $\varphi(101) = 100$; сокращение по 101 даёт другое, неверное число.
• Читают двоичную запись не с того конца. В способе справа налево младший бит соответствует $a^1$, в способе слева направо разбор начинается со старшего бита. Смешение порядков даёт правдоподобный, но неверный остаток.

FAQ

Сколько умножений нужно для показателя из 2048 бит? Квадрирований будет 2047, домножений в среднем около половины от числа бит, то есть примерно 1024. Итого порядка трёх тысяч умножений вместо астрономических $2^{2048}$. Именно эта разница делает работоспособной криптографию с открытым ключом.

Чем быстрое возведение отличается от бинарного и дихотомического? Ничем: это три названия одного алгоритма. Встречаются также термины «возведение в степень методом квадрирования» и английское square and multiply.

Можно ли обойтись без таблицы квадратов? Да, для этого и нужен проход слева направо: он хранит единственный остаток и делает то же число умножений. Таблица удобна на бумаге, когда решение нужно показать целиком.

Что делать, если модуль составной? Сам алгоритм не меняется, он не требует простоты модуля. Отличается только предварительное сокращение показателя: вместо $m - 1$ берётся $\varphi(m)$, а для модуля вида $m = pq$ расчёт часто разбивают по китайской теореме об остатках и считают две степени по меньшим модулям.

Коротко

1. Разложить показатель в двоичную запись: $93 = 1011101_2$, единицы стоят на местах $2^0, 2^2, 2^3, 2^4, 2^6$.
2. Построить таблицу квадратов по модулю: 7, 49, 78, 24, 71, 92, 81 - каждая строка есть квадрат предыдущей, приведённый по модулю 101.
3. Перемножить строки с единичными битами, приводя по модулю после каждого умножения: $7 \to 41 \to 75 \to 73 \to 55$.
4. Ответ: $7^{93} \equiv 55 \pmod{101}$ за 10 умножений против 92 при перемножении в лоб; общая оценка равна $\lfloor \log_2 n \rfloor + s(n) - 1$.
5. Проверить результат малой теоремой Ферма: $55 \cdot 7^{7} \equiv 55 \cdot 90 \equiv 1 \pmod{101}$.