Быстрое возведение в степень
a^n за log n умножений: биты экспоненты + возведение в квадрат.
1function power(base: number, exp: number, mod: number): number {2 let result = 13 let b = base % mod4 let e = exp5 6 while (e > 0) {7 if (e & 1) result = (result * b) % mod // бит установлен — умножаем8 b = (b * b) % mod // степень квадратом9 e >>= 110 }11 12 return result13}14// 3^13 = 3^8 · 3^4 · 3^1 — биты экспонентыПроблема
a^n за log n умножений: биты экспоненты + возведение в квадрат.
Что вы видите
13 = 1101₂: результат умножается только на степенях с битом 1.
Как это работает
Каждый шаг возводит в квадрат и сдвигает экспоненту. С модулем — криптография; без — числа растут, но шагов всё равно log.
Пошаговый разбор
- 01
Биты
Экспонента в двоичном.
- 02
Квадрат
b ← b² каждый шаг.
- 03
Умножение
Бит 1 — результат ×b.
Complexity и ограничения
Сложность см. в шапке страницы.
Edge cases
- Пустой вход
Корректная тривиальная обработка.
- Вырожденный случай
Минимум работы — сразу ответ.
Где встречается в реальности
RSA
Шифрование на сотнях бит.
Диффи-Хеллман
Обмен ключами.
Хеши
Полиномиальные по модулю.
Связанные алгоритмы
«3^13 за 4 умножения»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.