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

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

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

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

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

Описание

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

Пусть

${\displaystyle n=({\overline {m_{k}m_{k-1}...m_{1}m_{0}}})_{2}}$ — двоичное представление степени n, то есть,

${\displaystyle n=m_{k}\cdot 2^{k}+m_{k-1}\cdot 2^{k-1}+\dots +m_{1}\cdot 2+m_{0},}$

где ${\displaystyle m_{k}=1,m_{i}\in \{0,1\}}$. Тогда

${\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}}}$^[5].

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

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

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

${\displaystyle {\begin{Bmatrix}s_{1}=x\\s_{i+1}=s_{i}^{2}\cdot x^{m_{k-i}}\\i=1,2,\dots ,k\end{Bmatrix}}.}$

Обобщения

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

${\displaystyle a^{n}=\left\{{\begin{array}{ll}a&n=1\\a*\left(a^{n-1}\right)&n>1\end{array}}\right.}$

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

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

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

${\displaystyle 13_{10}=1101_{2}}$

${\displaystyle m_{3}=1,m_{2}=1,m_{1}=0,m_{0}=1}$

${\displaystyle {\begin{aligned}21^{13}&=(((21^{m_{3}})^{2}\cdot 21^{m_{2}})^{2}\cdot 21^{m_{1}})^{2}\cdot 21^{m_{0}}\\&=(((21^{1})^{2}\cdot 21^{1})^{2}\cdot 21^{0})^{2}\cdot 21^{1}\\&=((21^{2}\cdot 21)^{2}\cdot 1)^{2}\cdot 21\\&=((21^{2}\cdot 21)^{2})^{2}\cdot 21\\&=((441\cdot 21)^{2})^{2}\cdot 21\\&=85766121^{2}\cdot 21\\&=154472377739119461\end{aligned}}}$

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

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

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

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

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

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

${\displaystyle d=a^{n}=}$

${\displaystyle =a^{\sum _{i=0}^{k}m_{i}\cdot 2^{i}}=}$

${\displaystyle =a^{m_{0}}\cdot a^{2m_{1}}\cdot a^{2^{2}*m_{2}}\cdot ...\cdot a^{2^{k}*m_{k}}=}$

${\displaystyle =a^{m_{0}}\cdot (a^{2})^{m_{1}}\cdot (a^{2^{2}})^{m_{2}}\cdot ...\cdot (a^{2^{k}})^{m_{k}}=}$

${\displaystyle =\prod _{i=0}^{k}{(a^{2^{i}})^{m_{i}}}}$^[9].

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

i	0	1	2	3
${\displaystyle a^{2^{i}}}$	21	441	194 481	37 822 859 361
${\displaystyle m_{i}}$	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 в битах, ${\displaystyle k\sim \ln {n}}$. Количество же требуемых операций умножения равно весу Хэмминга, то есть количеству ненулевых элементов в двоичной записи числа n. В среднем требуется ${\displaystyle {\frac {1}{2}}\cdot \ln {n}}$ операций умножения^[6].

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

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

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

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

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

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

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

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

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

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

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

Для примера возведём методом скользящего окна число 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, схеме Эль-Гамаля и других криптографических алгоритмах^[11].

См. также

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

Примечания

1. Швец А. Н. Быстрое возведение в степень  (неопр.). Дата обращения: 13 ноября 2015. Архивировано 17 ноября 2015 года.
2. Панкратова, 2009, с. 7.
3. Панкратова, 2009, с. 11.
4. Панкратова, 2009, с. 10.
5. Рябко, Фионов, 2004.
6. Handbook, 2006.
7. Крэндалл, Померанс, 2011.
8. Криптография, 2005.
9. Габидулин, Кшевецкий, Колыбельников, 2011.
10. Маховенко, 2006.
11. Прикладная криптография, 2002.

Литература

• Шнайер Б. Алгоритмы с открытыми ключами // Прикладная криптография. — Триумф, 2002. — ISBN 5-89392-055-4.
• Рябко Б. Я., Фионов А. Н. Основы современной криптографии для специалистов в информационных технологиях — Научный мир, 2004. — С. 15. — 173 с. — ISBN 978-5-89176-233-6
• Смарт Н. Алгоритмы возведения в степень // Криптография. — Москва: Техносфера, 2005. — С. 287—292. — 528 с. — ISBN 5-94836-043-1.
• Маховенко Е. Б. Теоретико-числовые методы в криптографии — М.: Гелиос АРВ, 2006. — С. 154—155. — ISBN 978-5-85438-143-7
• Cohen H., Frey G. Handbook of Elliptic and Hyperelliptic Curve Cryptography. — Chapman & Hall/CRC, 2006. — С. 145—150. — 808 с. — ISBN 1-58488-518-1.
• Панкратова И. А. Теоретико-числовые методы криптографии — Томск: ТГУ, 2009. — 120 с.
• Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — С. 230—231. — 225 с. — ISBN 978-5-7417-0377-9
• Крэндалл Р., Померанс К. Алгоритмы с открытыми ключами // Простые числа: Криптографические и вычислительные аспекты — М.: URSS, 2011. — С. 514—520. — 663 с. — ISBN 978-5-453-00016-6, 978-5-397-02060-2