Очевидное или невероятное

В некоторых алгоритмах теории чисел возникает потребность возведения в степень по модулю: $$a^b \bmod m$$ Обозначение $\bmod m$ означает взятие остатка от деления на $m$. Нужно это так как вычисления происходят в конечной (из $m$ элементов) алгебраической структуре похожей на структуру целых чисел (и для того чтобы в этой структуре оставаться берется остаток от деления). В частности, это действие используется при проверке целого числа на простоту (на наличие или отсутствие у него нетривиальных делителей) для того, чтобы мы могли безопасно обмениваться сообщениями в интернете¹.

Есть другая близкая задача. Найти такое $b$ для которого $a^b \bmod m = x$. Другими словами, вычислить логарифм $\log_a x$, только по модулю $m$ - значит дискретный логарифм.

Вопрос: Насколько быстро эти действия (возведение в степень по модулю и дискретное логарифмирование) можно производить? Если речь идет о целых числах в записи которых, скажем, более 300 цифр ($\approx 2^{1024}$).

Наивные алгоритмы предполагают одинаковое количество шагов: начинаем вычислять $a^k \bmod m$ для $k=1,2,3,\ldots$ пока задача не будет выполнена. Это чрезвычайно большое количество (чтобы их выполнить не хватит и времени существования вселенной).

Ответ: В настоящее время учеными предполагается, что дискретное логарифмирование - трудная задачка, в то время как возведение в степень по модулю делается молниеносно и практически не зависит от самой величины степени.

Ну как так-то?! Ведь с логарифмом справляется любой калькулятор, правда в действительных числах.

Это во-первых, а во-вторых: ничего себе, как быстро! Например, для возведения числа $a$ в степень $10^{10}$ потребуется выполнить не более 66 умножений, а не 10000000000. Посмотрим, как это достигается.

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

Будем использовать двоичное представление $b = (b_s\, b_{s-1} \ldots b_1\, b_0)_2 = b_s \cdot 2^s + b_{s-1} \cdot 2^{s-1} + \ldots + b_1 \cdot 2 + b_0 \cdot 2^0$.

Тогда $a^b = a^{b_s \cdot 2^s + b_{s-1} \cdot 2^{s-1} + \ldots + b_1 \cdot 2 + b_0 \cdot 2^0}$ или $a^b = (a^{2^0})^{b_0} \cdot (a^{2^1})^{b_1} \cdot (a^{2^2})^{b_2} \cdot \ldots \cdot (a^{2^s})^{b_s}$, или $$a^b = a^{b_0} \cdot (a^{2})^{b_1} \cdot ((a^{2})^2)^{b_2} \cdot (((a^{2})^2)^2)^{b_3} \ldots \cdot ((a^{2^{s-1}})^{2})^{b_s}$$

Сколько бит в двоичном представлении $b$, столько и сомножителей. Можно заметить также, что сомножители получаются друг из друга возведением в квадрат: $a^{2^k} = a^{2^{k-1} \cdot 2} = (a^{2^{k-1}})^2$. И если очередной бит $b_k$ представления числа $b$ нулевой, то такой сомножитель вовсе пропускается.

Алгоритм быстрого возведения в степень:
сначала частичное произведение полагаем равным 1; для каждого $k=0,1,\ldots,s$:

1. Вычисляем очередной бит $b_k$ числа $b$: берем остаток от деления на 2
2. Если $b_k = 1$, то домножаем частичное произведение на $a^{2^k}$

prod = 1
ak = a

for k = 0,1,...,s:
    if b_binary[k] = 1:
        prod = prod * ak
    ak = ak * ak

В ходе выполнения потребуется сделать столько шагов, сколько двоичных цифр в $b$: это $\log_2(b)$; на каждом шаге нужно 2 умножения. Общее количество арифметических операций порядка $\log(b)$.

Поэтому, как и говорили в примере, $a^{10^{10}}$ всего за $33 \approx \log_2(10^{10})$ шага. Отдельный вопрос про то, что это может быть очень большое число. Но если мы говорим о вычислении в конечной структуре, то на каждом шаге можно и нужно брать остаток (приводить по модулю $m$) и результат перестанет быть совсем уж неразумным.

Но стоит ли удивляться тому, что может придумать любой студент (ну почти)? Действительно, ведь когда вы хитро вычисляете $a^8 = \underbrace{a \cdot a}_b \cdot \underbrace{a \cdot a}_b \cdot \underbrace{a \cdot a}_b \cdot \underbrace{a \cdot a}_b$, потом $a^8 = \underbrace{b \cdot b}_c \cdot \underbrace{b \cdot b}_c$, потом $a^8 = c \cdot c$, вы делаете именно то, что обсуждалось.

“Быстрое” умножение

А может быть так с любым произведением можно, не только со степенью? Это было бы удивительнее. Никогда не задумывался, но нечто подобное можно наблюдать и для привычного нам умножения. Называется умножение в столбик.

Наивный алгоритм умножения $a \cdot b$ предполагает, что мне следует складывать $a$ само с собой ровно $b$ раз. Что тоже может быть неподъемной задачей сложность которой - $b$ сложений.

Алгоритм “быстрого” умножения :)
всем хорошо известен: будем использовать десятичное представление $b = (b_s\, b_{s-1} \ldots b_1\, b_0)_{10} = b_s \cdot 10^s + b_{s-1} \cdot 10^{s-1} + \ldots + b_1 \cdot 10 + b_0 \cdot 10^0$

Тогда $a \cdot b = a \cdot (b_s \cdot 10^s + b_{s-1} \cdot 10^{s-1} + \ldots + b_1 \cdot 10 + b_0 \cdot 10^0)$ или $a \cdot b = a b_s \cdot 10^s + a b_{s-1} \cdot 10^{s-1} + \ldots + a b_1 \cdot 10 + a b_0 \cdot 10^0$.

Хотя обычно с $a$ мы также используем цифры десятичного представления.

При выполнении этого алгоритма мы совершаем лишь $\log_{10}(b)$ умножений и сложений, что заметно лучше в сравнении с $b$ сложениями.

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

Быстрое умножение

При всей важности операции умножения алгоритм умножения в столбик считался “быстрым” на протяжении почти всей истории. Вплоть до недавнего времени. Алгоритм быстрее существует и первым его представил (1962) А. А. Карацуба.

Алгоритм Карацубы предлагает использовать представление чисел $a = a_1 \cdot B^m + a_0$ и $b = b_1 \cdot B^m + b_0$ в некоторой системе счисления по основанию $B^m$. Тогда $a \cdot b = (a_1 \cdot B^m + a_0)(b_1 \cdot B^m + b_0)$ или $a \cdot b = a_1 b_1 B^{2m} + (a_1 b_0 + a_0 b_1) B^m + a_0 b_0$.

Здесь требуется 4 умножения, а выигрыш достигается путем вычисления $a_1 b_0 + a_0 b_1$ так:
$(a_1 + a_0)(b_1 + b_0)$ плюс $-a_1 b_1-a_0 b_0$ (эти произведения уже вычислены). В результате вместо 4 умножений используется 3.

Упоминается, что А. А. Карацуба предложил новый способ всего за неделю².

Другую важнейшую операцию очень хочется упомянуть в свете последних событий. Это умножение матриц³.

Умножение матриц существовало себе спокойно пока Ф. Штрассен (V. Strassen) не предложил (1969) алгоритм быстрее. Алгоритм Штрассена похож на алгоритм Карацубы. Но в октябре 2022 года в журнале Nature были опубликованы⁴ новые алгоритмы перемножения матриц, которые в некоторых случаях быстрее алгоритма Штрассена. Самое интересное в том, что этот результат получен с помощью искусственных нейронных сетей (искусственный интеллект т.е.)⁵.

Были и до этого доказанные компьютерами теоремы, но наконец-то искусственный интеллект применен в таком плане.