Модуль 20 ⏱ ~25 мин чтения 📐 1 Mermaid диаграмм

3. Быстрое возведение в степень

Введение: Почему линейный подход убивает производительность

Вычисление $a^b$ наивным циклом умножения res *= a, повторяющимся b раз, обладает линейной временной сложностью O(b). Для крошечных степеней вроде $2^8$ или $3^4$ этот подход незаметен. Однако в серверном бэкенде, алгоритмической криптографии и телеметрии экспоненты регулярно достигают значений порядка $10^{18}$ или разрастаются до 2048-битных ключей. При $b = 10^9$ наивный цикл выполнит один миллиард последовательных скалярных умножений, наглухо заблокировав поток операционной системы на сотни миллисекунд.

Алгоритм быстрого возведения в степень (известный в классической литературе как Binary Exponentiation или Exponentiation by Squaring) сокращает вычислительную сложность с O(b) до O(log b). Вместо миллиарда однотипных шагов нам потребуется всего около 30–60 операций. Это фундаментальный строительный блок криптографических протоколов (RSA, Diffie-Hellman), алгоритмов хеширования, полиномиальных генераторов псевдослучайных последовательностей и систем вычисления контрольных сумм.

Математическое ядро: Разложение по степеням двойки

Любое положительное целое число $b$ однозначно разлагается в двоичной системе счисления: $b = \sum_{i=0}^{k} b_i \cdot 2^i$, где каждый коэффициент $b_i \in \{0, 1\}$.
Следовательно, степень $a^b$ факторизуется в произведение:
$$a^b = a^{\sum b_i 2^i} = \prod_{b_i=1} a^{2^i}$$

Мы можем последовательно получать значения $a^{2^0}, a^{2^1}, a^{2^2}, \dots$ тривиальным возведением текущего основания в квадрат на каждом шаге. Если $i$-й бит экспоненты равен 1, мы просто умножаем накапливаемый результат на уже подготовленное число $a^{2^i}$.

Пример: Вычислим $a^{13}$. В двоичном представлении $13 = 1101_2 = 8 + 4 + 1$:

  1. $i=0$, бит = 1: $res = a^1$, $base = a^2$
  2. $i=1$, бит = 0: $res$ остается неизменным, $base = (a^2)^2 = a^4$
  3. $i=2$, бит = 1: $res = a^1 \cdot a^4 = a^5$, $base = (a^4)^2 = a^8$
  4. $i=3$, бит = 1: $res = a^5 \cdot a^8 = a^{13}$, $base = a^{16}$

Итого: ровно 4 итерации цикла вместо 12 последовательных умножений.

flowchart TD
    Start["Начало: res = 1, base = a, exp = b"] --> Check{"exp > 0?"}
    Check -->|"Нет"| End["Возврат res"]
    Check -->|"Да"| BitTest{"exp and 1 == 1?"}
    BitTest -->|"Да"| Mult["res = res * base"]
    BitTest -->|"Нет"| Skip["Пропуск умножения"]
    Mult --> Square
    Skip --> Square
    Square["base = base * base"] --> Shift["exp = exp >> 1 сдвиг вправо"]
    Shift --> Check

    style Start fill:#1e293b,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    style Check fill:#1e293b,stroke:#f59e0b,stroke-width:2px,color:#f8fafc
    style End fill:#1e293b,stroke:#10b981,stroke-width:2px,color:#f8fafc
    style BitTest fill:#1e293b,stroke:#a855f7,stroke-width:2px,color:#f8fafc
    style Mult fill:#1e293b,stroke:#6366f1,stroke-width:2px,color:#f8fafc
    style Skip fill:#1e293b,stroke:#64748b,stroke-width:2px,color:#f8fafc
    style Square fill:#1e293b,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    style Shift fill:#1e293b,stroke:#64748b,stroke-width:2px,color:#f8fafc

Production-реализация на Go 1.21+

В промышленном бэкенде редко требуется «чистое» неограниченное возведение в степень — целые числа мгновенно переполняют машинные регистры. Почти всегда задача сводится к модульной арифметике. Ниже представлена компактная, эффективная и безопасная реализация для uint64.

Go 
package mathalgo

// PowMod вычисляет (base^exp) % mod за O(log exp).
// Работает корректно только если mod != 0 и base*base не переполняет uint64 до взятия mod.
func PowMod(base, exp, mod uint64) uint64 {
    if mod == 0 {
        panic("powmod: mod cannot be zero")
    }
    if mod == 1 {
        return 0 // Любой остаток от деления на 1 равен 0
    }

    base %= mod
    res := uint64(1)

    for exp > 0 {
        if exp&1 == 1 { // Если младший бит установлен
            res = (res * base) % mod
        }
        base = (base * base) % mod
        exp >>= 1
    }

    return res
}

Ключевые инженерные решения:

  • Итеративный цикл: Никакой рекурсии. Рекурсивный вызов расходует кадры стека и создает оверхед на пролог/эпилог функций. Итеративный цикл выполняется исключительно в регистрах CPU.
  • Предварительное base %= mod: Гарантирует, что первое же промежуточное умножение не вызовет переполнения, если исходный base превышал mod.
  • Защита от mod == 1: Немедленный возврат нуля предотвращает паразитное деление на единицу, которое компилятор не всегда способен устранить.

Для работы с криптографическими числами произвольной разрядности используйте стандартный метод math/big.Int.Exp. Однако помните: каждый вызов big.Int аллоцирует память в куче. В горячих путях микросервисов структуры big.Int обязательно переиспользуют через sync.Pool.

Mechanical Sympathy: Регистры, предсказание ветвлений и аллокации

Поведение PowMod на физическом кремнии отражает гармонию математической логики и микроархитектуры современных CPU.

Регистровое давление и отсутствие аллокаций

Тело цикла for exp > 0 задействует ровно 3 локальные переменные: base, exp, res. Компилятор Go безупречно аллоцирует их в регистрах общего назначения (RAX, RBX, RCX на архитектуре x86-64). Здесь нет ни единого обращения к оперативной памяти, ни байта в куче и нулевое воздействие на сборщик мусора. Временная и пространственная сложность идеальны: $O(1)$ по памяти.

Ветвления и CMOV

Проверка if exp&1 == 1 компилируется в условный переход JZ (Jump if Zero). Если биты показателя степени случайны (как в криптографических ключах), предсказатель ветвлений процессора (Branch Predictor) ошибается с вероятностью до ~50%, вызывая сброс конвейера инструкций (pipeline stall). Компилятор Go 1.21+ в ряде ситуаций заменяет такие ветвления на инструкцию бескликного условного перемещения CMOV. Однако при 64-битном умножении это затруднено влиянием на флаги процессора.

128-битная арифметика на amd64

Операция base = (base * base) % mod на платформе x86-64 превращается в элегантную аппаратную последовательность инструкций:

  1. MULQ base — перемножает 64-битные регистры, сохраняя полный 128-битный результат в регистровую пару RDX:RAX (старшие и младшие 64 бита соответственно).
  2. DIVQ mod — выполняет 128-битное деление пары RDX:RAX на делитель mod, возвращая частное в RAX, а искомый остаток — в регистр RDX.

Эти микроинструкции выполняются процессором за 20–40 тактов. Без аппаратной поддержки деления паре пришлось бы выполнять программную эмуляцию длинной арифметики, что работало бы в 5–10 раз медленнее.

Криптография и атаки по времени (Timing Attacks)

Базовый алгоритм PowMod выполняется за переменное время в зависимости от количества единичных бит в числе exp. Если показатель содержит 32 установленных бита, цикл выполнит 32 модульных умножения. Если единиц всего 4 — алгоритм отработает значительно быстрее.

В криптографии с открытым ключом (RSA, Diffie-Hellman, ECDSA) сетевой злоумышленник может с наносекундной точностью измерять время ответа сервиса и по задержкам побитово реконструировать закрытый ключ. Это хрестоматийный пример сторонней атаки по времени (side-channel attack).

Для защиты в криптографических ядрах реализуется Constant-Time логика, где вычисления происходят за фиксированное число тактов без каких-либо ветвлений:

Go 
func PowModCT(base, exp, mod uint64) uint64 {
    base %= mod
    res := uint64(1)
    for exp > 0 {
        // Маска равна 18446744073709551615 если exp&1==1, иначе 0
        mask := -(exp & 1) 
        // Умножаем res на base только если маска полная
        // В production используют ассемблер или crypto/subtle для гарантированной константности
        res = res ^ (mask & (res ^ ((res * base) % mod)))
        base = (base * base) % mod
        exp >>= 1
    }
    return res
}

В реальном промышленном коде на Go никогда не изобретайте самодельные криптографические примитивы. Всегда опирайтесь на пакеты стандартной библиотеки crypto/rsa, crypto/elliptic и вспомогательный пакет crypto/subtle, где константное время исполнения верифицировано и защищено на уровне ассемблерных вставок.

Ловушки и вопросы с собеседований

Итог

  • Быстрое возведение в степень радикально снижает вычислительную сложность операции $a^b$ с O(b) до O(log b) путем разложения показателя по степеням двойки.
  • В бэкенд-разработке алгоритм практически всегда работает в форме модульной арифметики (PowMod), предотвращая переполнение регистров взятием остатка на каждой итерации.
  • Реализация на Go выполняется исключительно в CPU-регистрах, свободна от аллокаций в куче и требует O(1) по памяти. Компилятор задействует аппаратные 128-битные инструкции MULQ/DIVQ.
  • Криптографическая безопасность: проверка младшего бита if exp&1 == 1 уязвима к тайминг-атакам. В промышленной криптографии применяются constant-time алгоритмы пакетов crypto/ и math/big.
  • Интервью-фокус: знание связи с малой теоремой Ферма, механизмы предотвращения overflow, обобщение на умножение матриц и четкое понимание границ применимости math.Pow.
  • Связь с теорией чисел: быстрый алгоритм возведения в степень идет рука об руку с алгоритмами нахождения наибольшего общего делителя для проверки взаимной простоты и вычисления модульных мультипликативных инверсий.

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

4. Алгоритм Евклида и GCD