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

Посчитайте 3 в степени 10¹⁸ — точнее, остаток от деления этого числа на миллиард семь. Если умножать на три подряд, понадобится миллиард миллиардов умножений: при миллиарде умножений в секунду — тридцать с лишним лет. А алгоритм ниже делает это за 84 умножения. Он смотрит на показатель в двоичной системе, и каждая двоичная цифра стоит ему одно возведение в квадрат и, если цифра — единица, одно домножение.

Поменяйте показатель. Шагов столько, сколько цифр в двоичной записи, а подсвеченных ступенек — столько, сколько в ней единиц. Миллиард миллиардов — это 60 двоичных цифр, 24 из них единицы, отсюда 60 + 24 = 84.

Идея

a¹³ = a⁸ · a⁴ · a¹, потому что 13 = 1101₂. Степени вида a, a², a⁴, a⁸, … получаются друг из друга одним возведением в квадрат, а нужные из них выбирают единицы в двоичной записи показателя.

То же самое можно сказать рекурсивно: aⁿ = (a^n/2)² для чётного n и aⁿ = a · aⁿ⁻¹ для нечётного. Каждые два шага показатель уменьшается хотя бы вдвое — это разделяй и властвуй в одну строчку. Итеративная запись удобнее: идём по битам справа налево, держим текущий квадрат и текущий ответ.

Главное в задачах «по модулю»: брать остаток после каждого умножения. Остаток произведения равен остатку произведения остатков, так что ответ не меняется, зато числа никогда не вырастают больше m². Без этого 3^10¹⁸ — число примерно из 4,8·10¹⁷ десятичных цифр: его не уместить ни в какую память.

Код

В Python это встроено: pow(a, n, m) с тремя аргументами делает ровно это. В Go — big.Int.Exp для больших чисел. Для обычных uint64 функцию пишут сами, и тут есть ловушка: произведение двух остатков по модулю около 10⁹ помещается в 64 бита, а по модулю около 10¹⁸ — уже нет. Для больших модулей нужно умножение со 128-битным результатом (bits.Mul64) или math/big.

Последняя строка вывода — обратный элемент. По малой теореме Ферма для простого p число a^p−1 даёт остаток 1, значит, a^p−2 — обратный к a. Это второй способ делить по модулю, кроме расширенного алгоритма Евклида, — но только для простого модуля.

Почему умножений так мало

Пусть в двоичной записи n всего k = ⌊log₂ n⌋ + 1 цифр, и s из них единицы. Цикл делает k итераций, в каждой одно возведение в квадрат, а домножение — только на единицах: k + s ≤ 2k умножений. Для n около 10¹⁸ это не больше 120.

Меньше в общем случае почти нельзя: за одно умножение степень показателя может самое большее удвоиться, поэтому чтобы получить aⁿ, нужно хотя бы log₂ n умножений. Бывают и хитрые цепочки сложений, которые экономят часть домножений, — их ищут для фиксированных больших показателей в криптографии, — но порядок log n остаётся.

Ключ, о котором договорились у всех на виду

Самое важное применение быстрого возведения в степень работает каждый раз, когда вы открываете защищённое соединение. Двум сторонам нужно договориться об общем секретном ключе, но любой их обмен может быть подслушан. В 1976 году Уитфилд Диффи и Мартин Хеллман предложили способ:

1. Все знают большое простое p и число g.
2. Алиса выбирает секрет a и открыто отправляет A = gᵃ mod p. Боб выбирает секрет b и отправляет B = gᵇ mod p.
3. Алиса вычисляет Bᵃ, Боб — Aᵇ. Оба получили g^ab mod p — общий ключ.

Ниже настоящее простое число из стандарта RFC 3526 — 2048 бит, больше шестисот десятичных цифр. Им до сих пор пользуется SSH. Секреты такой же длины выбирает генератор случайных чисел вашего браузера.

Посмотрите на время: четыре возведения в степень 2048-битного числа — доли секунды прямо в браузере, около трёх тысяч умножений на каждое. А Ева видит p, g, A и B, и чтобы найти ключ, ей нужно по A восстановить a. Это задача дискретного логарифма, и для таких чисел её не умеют решать за разумное время. Вся схема держится на асимметрии: возводить в степень по модулю легко, логарифмировать — трудно.

Ту же операцию использует RSA: шифрование — это mᵉ mod N, расшифровка — c^d mod N. Об этом вторая задача.

Сколько это стоит

O(log n) умножений. Если числа помещаются в машинное слово, каждое умножение — O(1), и всё возведение — несколько десятков тактов. Для длинных чисел из L бит школьное умножение стоит O(L²), поэтому возведение в степень с L-битным показателем по L-битному модулю — O(L³). Для 2048 бит это миллиарды элементарных операций — и всё равно доли секунды.

Не только числа

Алгоритму всё равно, что умножать, лишь бы умножение было ассоциативным. Матрицы — пожалуйста: возведение матрицы [[1, 1], [1, 0]] в степень n даёт числа Фибоначчи, и n-е число Фибоначчи по модулю считается за O(log n) — первая задача, а подробно — матрицы и рекуррентности. Перестановки — за log n шагов можно узнать, где окажется карта после миллиарда одинаковых тасовок. Многочлены, преобразования, путь длины n в графе — везде, где есть «сделать одно и то же n раз», подходит та же лесенка квадратов.

История

Приём древний. Дональд Кнут в «Искусстве программирования» указывает, что он встречается ещё в трактате Пингалы о стихосложении, написанном раньше 200 года до нашей эры: там так считают 2ⁿ — число возможных ритмов из n слогов. В вычислительную технику он пришёл вместе с первыми компьютерами и стал незаметной основой криптографии с открытым ключом.

Задачи

В первой задаче возводить в степень придётся матрицу. Во второй — собрать игрушечный RSA целиком: Евклид, быстрое возведение и одна ловушка с переполнением.