Алгоритмы быстрого возведения в степень ( дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы , предназначенные для возведения числа ${\displaystyle x}$ в натуральную степень ${\displaystyle n}$ за меньшее число умножений , чем это требуется в определении степени . Многие из этих алгоритмов основаны на том, что для возведения числа ${\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}}$ ).

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

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

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

Описание

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

Пусть

${\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}}}$ .

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

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

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

${\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 ⁿ в любой полугруппе (в абелевой группе в частности) можно использовать алгоритмы быстрого возведения в степень .

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

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

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

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

${\displaystyle {\begin{aligned}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\cdot 21)^{2})^{2}\cdot 21\\&=85766121^{2}\cdot 21\\&=154472377739119461\end{aligned}}}$

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

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

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

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

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

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

${\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}}}}$ .

Пример . Посчитаем с помощью схемы возведения в степень «справа налево» значение 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}}$ операций умножения .

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

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

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

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

Окно фактически представляет собой основание системы счисления . Пусть 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}}}$ .

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

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

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 возвести в квадрат .

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

Для примера возведём методом скользящего окна число 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 .
• , — , 2004. — С. 15. — 173 с. — ISBN 978-5-89176-233-6
• Смарт Н. Алгоритмы возведения в степень // . — Москва: Техносфера, 2005. — С. —292. — 528 с. — ISBN 5-94836-043-1 .
• — М. : , 2006. — С. 154—155. — ISBN 978-5-85438-143-7
• Cohen H., Frey G. . — Chapman & Hall/CRC, 2006. — С. —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