Быстрое возведение в степень: как посчитать 2 в миллионной без миллиона умножений

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

Один из тех случаев, когда «логарифм вместо линии» превращает невозможное в мгновенное.

Наивный способ

Чтобы вычислить $a^n$, школьный подход — умножить $a$ само на себя $n$ раз. Для $a^{1000}$ это 999 умножений. Терпимо. Но в криптографии показатели бывают порядка $2^{1024}$ — столько умножений физически не сделать никогда. Нужен принципиально иной счёт.

Ключевая идея: дели показатель пополам

Заметим простое тождество. Если показатель чётный, степень — это квадрат половинной степени. Если нечётный — то же самое плюс один множитель $a$:

$$a^n = \begin{cases} (a^{n/2})^2, & n \text{ чётное} \\ a \cdot a^{n-1}, & n \text{ нечётное} \end{cases}$$

Каждый шаг уполовинивает показатель. Чтобы посчитать $a^{1000}$, мы сводим его к $a^{500}$, затем к $a^{250}$, $a^{125}$ и так далее — до единицы. Всего около $\log_2 1000 \approx 10$ шагов вместо тысячи. Это та же магия деления пополам, что и в бинарном поиске, только применённая к арифметике.

Через биты показателя

Есть ещё красивее. Запишем показатель в двоичном виде. Например, $13 = 1101_2$, то есть $13 = 8 + 4 + 1$. Тогда

$$a^{13} = a^{8} \cdot a^{4} \cdot a^{1}$$

Мы идём по битам показателя справа налево, на каждом шаге возводя основание в квадрат ($a, a^2, a^4, a^8, \dots$), и подмешиваем текущий квадрат в ответ только там, где в показателе стоит единичный бит. Это и есть «бинарное возведение в степень».

def fast_pow(a, n):
    result = 1
    while n > 0:
        if n & 1:          # младший бит показателя = 1
            result *= a
        a *= a             # основание в квадрат: a, a^2, a^4, ...
        n >>= 1            # сдвигаем показатель на бит вправо
    return result

print(fast_pow(2, 10))     # 1024
print(fast_pow(3, 13))     # 1594323
print(fast_pow(2, 64))     # 18446744073709551616

# рекурсивная форма — та же идея «дели показатель пополам»
def pow_rec(a, n):
    if n == 0:
        return 1
    half = pow_rec(a, n // 2)
    return half * half * (a if n % 2 else 1)

print(pow_rec(5, 5))       # 3125

Сколько умножений на самом деле

Для показателя $n$ алгоритм делает порядка $\log_2 n$ возведений в квадрат и не больше столько же домножений — итого $O(\log n)$ операций. Сравните: для $n = 1{,}000{,}000$ наивный путь — миллион умножений, быстрый — около сорока. Это не оптимизация на проценты, это смена класса сложности.

Почему без этого нет криптографии

В RSA шифрование — это вычисление $m^e \bmod N$, где показатель и модуль — числа в сотни цифр. Каждое умножение к тому же берётся по модулю, чтобы числа не разрослись. Без быстрого возведения операция заняла бы астрономическое время; с ним — доли секунды. Тот же приём (matrix exponentiation) позволяет за логарифм считать $n$-е число Фибоначчи и применяется в динамике на больших числах.

Мораль

Быстрое возведение в степень — образцовая иллюстрация принципа «разделяй и властвуй»: задача размера $n$ сводится к задаче размера $n/2$, и логарифм возникает сам собой. Стоит увидеть в показателе его двоичную запись — и тысяча умножений сжимается до десятка. Этот сдвиг мышления, от «повторить n раз» к «удвоить $\log n$ раз», окупается в десятках алгоритмов.