Алгоритмы быстрого возведения в степень

Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа [math]\displaystyle{ x }[/math] в натуральную степень [math]\displaystyle{ n }[/math] за меньшее число умножений, чем это требуется в определении степени. Многие из этих алгоритмов основаны на том, что для возведения числа [math]\displaystyle{ x }[/math] в степень [math]\displaystyle{ n }[/math] не обязательно перемножать число [math]\displaystyle{ x }[/math] на само себя [math]\displaystyle{ n }[/math] раз, а можно перемножать уже вычисленные степени. В частности, если [math]\displaystyle{ n=2^k }[/math] степень двойки, то для возведения в степень [math]\displaystyle{ n }[/math] достаточно число возвести в квадрат [math]\displaystyle{ k }[/math] раз, затратив при этом [math]\displaystyle{ k }[/math] умножений вместо [math]\displaystyle{ 2^k }[/math]. Например, чтобы возвести число [math]\displaystyle{ x }[/math] в восьмую степень, вместо выполнения семи умножений [math]\displaystyle{ x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x }[/math] можно возвести число в квадрат ([math]\displaystyle{ x^2=x\cdot x }[/math]), потом результат возвести ещё раз в квадрат и получить четвёртую степень ([math]\displaystyle{ x^4=x^2\cdot x^2 }[/math]), и наконец результат ещё раз возвести в квадрат и получить ответ ([math]\displaystyle{ x^8=x^4\cdot x^4 }[/math]).

Кроме того, некоторые алгоритмы для дальнейшей оптимизации используют тот факт, что операция возведения в квадрат быстрее операции умножения за счёт того, что при возведении в квадрат цифры в сомножителе повторяются.

Бинарный алгоритм возведения в степень был впервые предложен в XV веке персидским математиком Аль-Каши.

Данные алгоритмы не всегда оптимальны. Например, при использовании схемы «слева направо» быстрое возведение в степень n = 15 потребует выполнения трёх операций умножения и трёх операций возведения в квадрат, хотя возведение в 15-ю степень можно выполнить и за 3 умножения и 2 возведения в квадрат. Оптимальное возведение в степень соответствует построению кратчайшей аддитивной цепочки.

Описание

Основным алгоритмом быстрого возведения в степень является схема «слева направо». Она получила своё название вследствие того, что биты показателя степени просматриваются слева направо, то есть от старшего к младшему.

Пусть

[math]\displaystyle{ n=(\overline {m_{k}m_{k-1}...m_{1}m_{0}})_2 }[/math] — двоичное представление степени n, то есть,

[math]\displaystyle{ n=m_{k} \cdot 2^{k}+m_{k-1} \cdot 2^{k-1}+\dots+m_{1} \cdot 2+m_{0}, }[/math]

где [math]\displaystyle{ m_{k}=1, m_{i} \in \{ 0,1 \} }[/math]. Тогда

[math]\displaystyle{ x^{n}=x^{((\dots((m_{k} \cdot 2+m_{k-1}) \cdot 2+m_{k-2}) \cdot 2+\dots) \cdot 2+m_{1}) \cdot 2 + m_{0}}=((\dots(((x^{m_{k}})^{2} \cdot x^{m_{k-1}})^{2}\dots)^{2} \cdot x^{m_{1}})^2 \cdot x^{m_{0}} }[/math].

Последовательность действий при использовании данной схемы можно описать так:

1. Представить показатель степени n в двоичном виде
2. Если [math]\displaystyle{ m_i }[/math] = 1, то текущий результат возводится в квадрат и затем умножается на x. Если [math]\displaystyle{ m_i }[/math] = 0, то текущий результат просто возводится в квадрат. Индекс i изменяется от k-1 до 0.

Таким образом, алгоритм быстрого возведения в степень сводится к мультипликативному аналогу схемы Горнера:

[math]\displaystyle{ \begin{Bmatrix} s_1=x \\ s_{i+1}=s_i^2 \cdot x^{m_{k-i}} \\ i=1,2,\dots,k \end{Bmatrix}. }[/math]

Обобщения

Пусть пара (S, *) — полугруппа, тогда мы можем назвать операцию * умножением и определить операцию возведения в натуральную степень:

[math]\displaystyle{ a^n=\left\{ \begin{array}{ll} a & n = 1 \\ a * \left(a^{n-1}\right) & n \gt 1 \end{array} \right. }[/math]

Тогда для вычисления значений aⁿ в любой полугруппе (в абелевой группе в частности) можно использовать алгоритмы быстрого возведения в степень.

Примеры решения задач

Применяя алгоритм, вычислим 21¹³:

[math]\displaystyle{ 13_{10} = 1101_2 }[/math]

[math]\displaystyle{ m_3=1, m_2=1, m_1=0, m_0=1 }[/math]

[math]\displaystyle{ \begin{align} 21^{13} & = ((( 1 \cdot 21^{m_3} )^2 \cdot 21^{m_2} )^2 \cdot 21^{m_1}) ^2 \cdot 21^{m_0} \\ & = ((( 1 \cdot 21^1 )^2 \cdot 21^1 )^2 \cdot 21^0) ^2 \cdot 21^1 \\ & = ((( 1 \cdot 21 )^2 \cdot 21 )^2 \cdot 1) ^2 \cdot 21 \\ & = ((21^2 \cdot 21)^2)^2 \cdot 21 \\ & = ((441\cdot21)^2)^2\cdot21 \\ & = 85766121^2\cdot21 \\ & = 154472377739119461 \end{align} }[/math]

Схема «справа налево»

В данной схеме, в отличие от схемы «слева направо», биты показателя степени просматриваются от младшего к старшему.

Последовательность действий при реализации данного алгоритма.

1. Представить показатель степени n в двоичном виде.
2. Положить вспомогательную переменную z равной числу x.
   1. Если [math]\displaystyle{ m_i=1 }[/math], то текущий результат умножается на z, а само число z возводится в квадрат. Если [math]\displaystyle{ m_i }[/math] = 0, то требуется только возвести z в квадрат. При этом индекс i, в отличие от схемы слева направо, изменяется от 0 до k-1 включительно.

Данная схема содержит столько же умножений и возведений в квадрат, сколько и схема «слева направо». Однако несмотря на это, схема «слева направо» выгоднее схемы «справа налево», особенно в случае, если показатель степени содержит много единиц. Дело в том, что в схеме слева направо в операции result = result · x содержится постоянный множитель x. А для небольших x (что нередко бывает в тестах простоты) умножение будет быстрым. К примеру, для x = 2 мы можем операцию умножения заменить операцией сложения.

Математическое обоснование работы данного алгоритма можно представить следующей формулой:

[math]\displaystyle{ d = a^n = }[/math]

[math]\displaystyle{ = a^{\sum_{i=0}^k m_i\cdot 2^i} = }[/math]

[math]\displaystyle{ = a^{m_0}\cdot a^{2m_1}\cdot a^{2^2*m_2}\cdot ... \cdot a^{2^k*m_k}= }[/math]

[math]\displaystyle{ = a^{m_0}\cdot (a^2)^{m_1}\cdot (a^{2^2})^{m_2}\cdot ... \cdot (a^{2^k})^{m_k}= }[/math]

[math]\displaystyle{ = \prod_{i=0}^k {(a^{2^{i}})^{m_i}} }[/math].

Пример. Посчитаем с помощью схемы возведения в степень «справа налево» значение 21¹³.

i	0	1	2	3
[math]\displaystyle{ a^{2^{i}} }[/math]	21	441	194 481	37 822 859 361
[math]\displaystyle{ m_i }[/math]	1	0	1	1

1. 21 · 194 481 = 4084 101
2. 4084 101 · 37 822 859 361 = 154 472 377 739 119 461

Вычислительная сложность

И для схемы «слева направо», и для схемы «справа налево» количество операций возведения в квадрат одинаково и равно k, где k — длина показателя степени n в битах, [math]\displaystyle{ k \sim \ln{n} }[/math]. Количество же требуемых операций умножения равно весу Хэмминга, то есть количеству ненулевых элементов в двоичной записи числа n. В среднем требуется [math]\displaystyle{ \frac{1}{2}\cdot\ln{n} }[/math] операций умножения.

Например, для возведения числа в сотую степень этим алгоритмом потребуется всего лишь 8 операций умножения и возведения в квадрат.

Для сравнения, при стандартном способе возведения в степень требуется [math]\displaystyle{ n-1 }[/math] операция умножения, то есть количество операций может быть оценено как [math]\displaystyle{ O(n) }[/math].

Оптимизация алгоритма

Как правило, операция возведения в квадрат выполняется быстрее операции умножения. Метод окон позволяет сократить количество операций умножения и, следовательно, сделать алгоритм возведения в степень более оптимальным.

Окно фактически представляет собой основание системы счисления. Пусть w — ширина окна, то есть за один раз учитывается w знаков показателя.

Рассмотрим метод окна.

1. Для [math]\displaystyle{ i = \overline {0, 2^w-1} }[/math] заранее вычисляется xⁱ
2. Показатель степени представляется в следующем виде: [math]\displaystyle{ n = \sum_{i=0}^{k/w}{n_i\cdot2^{i\cdot w}} }[/math], где [math]\displaystyle{ n_i \in {(0, 1, ..., 2^w-1)} }[/math]
3. Пусть y — переменная, в которой будет вычислен конечный результат. Положим [math]\displaystyle{ y=x^{n_{k/w}} }[/math].
4. Для всех i = k/w — 1, k/w — 2, …, 0 выполнить следующие действия:
   1. [math]\displaystyle{ y = y^{2^w} }[/math]
   2. [math]\displaystyle{ y = y\cdot x^{n_i} }[/math].

В данном алгоритме требуется k возведений в квадрат, но число умножений в среднем сокращается до k/w.

Ещё более эффективным является метод скользящего окна. Он заключается в том, что ширина окна во время выполнения процесса может изменяться:

1. Показатель степени представляется в виде [math]\displaystyle{ n = \sum_{i=0}^{l}{n_i\cdot2^{e_i}} }[/math], где [math]\displaystyle{ n_i \in {(1, 3, 5, ..., 2^w-1)} }[/math], а e_i+1 — e_i ≥ w.
2. Для [math]\displaystyle{ i = (1, 3, 5, ..., 2^w-1) }[/math] вычисляется xⁱ. Далее будем обозначать xⁱ как x_i.
3. Пусть y — переменная, в которой будет вычислен конечный результат. Положим [math]\displaystyle{ y=x^{n_{l}} }[/math].
4. Для всех i = l — 1, l — 2, …, 0 выполнить следующие действия:
   1. Для всех j от 0 до e_i+1 — e_i — 1 y возвести в квадрат
   2. [math]\displaystyle{ j = m_i }[/math]
   3. [math]\displaystyle{ y = y\cdot x_j }[/math]
5. Для всех j от 0 до e₀ — 1 y возвести в квадрат.

Количество операций возведения в степень в данном алгоритме такое же, как и в методе окна, а вот количество операций умножений сократилось до l, то есть до [math]\displaystyle{ \frac{k}{w+1} }[/math] в среднем.

Для примера возведём методом скользящего окна число x в степень 215. Ширина окна w = 3.

1. 215 = 2⁷ + 5 · 2⁴ + 7
2. y = 1
3. y = y · x = x
4. y 3 раза возводится в квадрат, так как на данном шаге e₂ — e₁ −1 = 7 — 4 — 1 = 2, а отсчёт ведётся с нуля, то есть y = y⁸ = x⁸
5. y = y · x⁵ = x¹³
6. y 4 раза возводится в квадрат, так как на данном шаге e₁ — e₀ −1 = 4 — 0 — 1 = 3, то есть y = y¹⁶= x²⁰⁸
7. y = y · x⁷ = x²¹⁵

Применение

Алгоритм быстрого возведения в степень получил широкое распространение в криптосистемах с открытым ключом. В частности, алгоритм применяется в протоколе RSA, схеме Эль-Гамаля и других криптографических алгоритмах.

См. также

• Возведение в степень по модулю
• Алгоритмы быстрого возведения в степень по модулю

Литература

• Шнайер Б. Алгоритмы с открытыми ключами // Прикладная криптография. — Триумф, 2002. — ISBN 5-89392-055-4.
• Шаблон:Source
• Смарт Н. Алгоритмы возведения в степень // Криптография. — Москва: Техносфера, 2005. — С. 287—292. — 528 с. — ISBN 5-94836-043-1.
• Шаблон:Source
• Cohen H., Frey G. Handbook of Elliptic and Hyperelliptic Curve Cryptography. — Chapman & Hall/CRC, 2006. — С. 145—150. — 808 с. — ISBN 1-58488-518-1.
• Шаблон:Source
• Шаблон:Source
• Шаблон:Source