Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа x {displaystyle x} в натуральную степень n {displaystyle n} за меньшее число умножений, чем это требуется в определении степени. Алгоритмы основаны на том, что для возведения числа x {displaystyle x} в степень n {displaystyle n} не обязательно перемножать число x {displaystyle x} на само себя n {displaystyle n} раз, а можно перемножать уже вычисленные степени. В частности, если n = 2 k {displaystyle n=2^{k}} степень двойки, то для возведения в степень n {displaystyle n} достаточно число возвести в квадрат k {displaystyle k} раз, затратив при этом k {displaystyle k} умножений вместо 2 k {displaystyle 2^{k}} . Например, чтобы возвести число x {displaystyle x} в восьмую степень, вместо выполнения семи умножений x ⋅ x ⋅ x ⋅ x ⋅ x ⋅ x ⋅ x ⋅ x {displaystyle xcdot xcdot xcdot xcdot xcdot xcdot xcdot x} можно возвести число в квадрат ( x 2 = x ⋅ x {displaystyle x^{2}=xcdot x} ), потом результат возвести ещё раз в квадрат и получить четвёртую степень ( x 4 = x 2 ⋅ x 2 {displaystyle x^{4}=x^{2}cdot x^{2}} ), и наконец результат ещё раз возвести в квадрат и получить ответ ( x 8 = x 4 ⋅ x 4 {displaystyle x^{8}=x^{4}cdot x^{4}} ).
Кроме того, некоторые алгоритмы для дальнейшей оптимизации используют тот факт, что операция возведения в квадрат быстрее операции умножения за счёт того, что при возведении в квадрат цифры в сомножителе повторяются.
Бинарный алгоритм возведения в степень был впервые предложен в XV веке персидским математиком Аль-Каши.
Данные алгоритмы не всегда оптимальны. Например, при использовании схемы «слева направо» быстрое возведение в степень n = 15 потребует выполнения трёх операций умножения и трёх операций возведения в квадрат, хотя возведение в 15-ю степень можно выполнить и за 3 умножения и 2 возведения в квадрат. Оптимальное возведение в степень соответствует построению кратчайшей аддитивной цепочки.
Описание
Основным алгоритмом быстрого возведения в степень является схема «слева направо». Она получила своё название вследствие того, что биты показателя степени просматриваются слева направо, то есть от старшего к младшему.
Пусть
n = ( m k m k − 1 . . . m 1 m 0 ¯ ) 2 {displaystyle n=({overline {m_{k}m_{k-1}...m_{1}m_{0}}})_{2}} — двоичное представление степени n, то есть, n = m k ⋅ 2 k + m k − 1 ⋅ 2 k − 1 + ⋯ + m 1 ⋅ 2 + m 0 , {displaystyle n=m_{k}cdot 2^{k}+m_{k-1}cdot 2^{k-1}+dots +m_{1}cdot 2+m_{0},}где m k = 1 , m i ∈ { 0 , 1 } {displaystyle m_{k}=1,m_{i}in {0,1}} . Тогда
x n = x ( ( … ( ( m k ⋅ 2 + m k − 1 ) ⋅ 2 + m k − 2 ) ⋅ 2 + … ) ⋅ 2 + m 1 ) ⋅ 2 + m 0 = ( ( … ( ( ( x m k ) 2 ⋅ x m k − 1 ) 2 … ) 2 ⋅ x m 1 ) 2 ⋅ x m 0 {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}}} .Последовательность действий при использовании данной схемы можно описать так:
Таким образом, алгоритм быстрого возведения в степень сводится к мультипликативному аналогу схемы Горнера:
{ s 1 = x s i + 1 = s i 2 ⋅ x m k − i i = 1 , 2 , … , k } . {displaystyle {egin{Bmatrix}s_{1}=xs_{i+1}=s_{i}^{2}cdot x^{m_{k-i}}i=1,2,dots ,kend{Bmatrix}}.}Обобщения
Пусть пара (S, *) — полугруппа, тогда мы можем назвать операцию * умножением и определить операцию возведения в натуральную степень:
a n = { a n = 1 a ∗ ( a n − 1 ) n > 1 {displaystyle a^{n}=left{{egin{array}{ll}a&n=1a*left(a^{n-1} ight)&n>1end{array}} ight.}Тогда для вычисления значений an в любой полугруппе (в абелевой группе в частности) можно использовать алгоритмы быстрого возведения в степень.
Примеры решения задач
Применяя алгоритм, вычислим 2113:
13 10 = 1101 2 {displaystyle 13_{10}=1101_{2}} m 3 = 1 , m 2 = 1 , m 1 = 0 , m 0 = 1 {displaystyle m_{3}=1,m_{2}=1,m_{1}=0,m_{0}=1} 21 13 = ( ( ( 1 ⋅ 21 m 3 ) 2 ⋅ 21 m 2 ) 2 ⋅ 21 m 1 ) 2 ⋅ 21 m 0 = ( ( ( 1 ⋅ 21 1 ) 2 ⋅ 21 1 ) 2 ⋅ 21 0 ) 2 ⋅ 21 1 = ( ( ( 1 ⋅ 21 ) 2 ⋅ 21 ) 2 ⋅ 1 ) 2 ⋅ 21 = ( ( 21 2 ⋅ 21 ) 2 ) 2 ⋅ 21 = ( ( 441 ⋅ 21 ) 2 ) 2 ⋅ 21 = 85766121 2 ⋅ 21 = 154472377739119461 {displaystyle {egin{aligned}21^{13}&=(((1cdot 21^{m_{3}})^{2}cdot 21^{m_{2}})^{2}cdot 21^{m_{1}})^{2}cdot 21^{m_{0}}&=(((1cdot 21^{1})^{2}cdot 21^{1})^{2}cdot 21^{0})^{2}cdot 21^{1}&=(((1cdot 21)^{2}cdot 21)^{2}cdot 1)^{2}cdot 21&=((21^{2}cdot 21)^{2})^{2}cdot 21&=((441cdot 21)^{2})^{2}cdot 21&=85766121^{2}cdot 21&=154472377739119461end{aligned}}}Схема «справа налево»
В данной схеме, в отличие от схемы «слева направо», биты показателя степени просматриваются от младшего к старшему.
Последовательность действий при реализации данного алгоритма.
Данная схема содержит столько же умножений и возведений в квадрат, сколько и схема «слева направо». Однако несмотря на это, схема «слева направо» выгоднее схемы «справа налево», особенно в случае, если показатель степени содержит много единиц. Дело в том, что в схеме слева направо в операции result = result · x содержится постоянный множитель x. А для небольших x (что нередко бывает в тестах простоты) умножение будет быстрым. К примеру, для x = 2 мы можем операцию умножения заменить операцией сложения.
Математическое обоснование работы данного алгоритма можно представить следующей формулой:
d = a n = {displaystyle d=a^{n}=} = a ∑ i = 0 k m i ⋅ 2 i = {displaystyle =a^{sum _{i=0}^{k}m_{i}cdot 2^{i}}=} = a m 0 ⋅ a 2 m 1 ⋅ a 2 2 ∗ m 2 ⋅ . . . ⋅ a 2 k ∗ m k = {displaystyle =a^{m_{0}}cdot a^{2m_{1}}cdot a^{2^{2}*m_{2}}cdot ...cdot a^{2^{k}*m_{k}}=} = a m 0 ⋅ ( a 2 ) m 1 ⋅ ( a 2 2 ) m 2 ⋅ . . . ⋅ ( 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}}=} = ∏ i = 0 k ( a 2 i ) m i {displaystyle =prod _{i=0}^{k}{(a^{2^{i}})^{m_{i}}}} .Пример. Посчитаем с помощью схемы возведения в степень «справа налево» значение 2113.
Вычислительная сложность
И для схемы «слева направо», и для схемы «справа налево» количество операций возведения в квадрат одинаково и равно k, где k — длина показателя степени n в битах, k ∼ ln n {displaystyle ksim ln {n}} . Количество же требуемых операций умножения равно весу Хэмминга, то есть количеству ненулевых элементов в двоичной записи числа n. В среднем требуется 1 2 ⋅ ln n {displaystyle {frac {1}{2}}cdot ln {n}} операций умножения.
Например, для возведения числа в сотую степень этим алгоритмом потребуется всего лишь 8 операций умножения и возведения в квадрат.
Для сравнения, при стандартном способе возведения в степень требуется n − 1 {displaystyle n-1} операция умножения, то есть количество операций может быть оценено как O ( n ) {displaystyle O(n)} .
Оптимизация алгоритма
Как правило, операция возведения в квадрат выполняется быстрее операции умножения. Метод окон позволяет сократить количество операций умножения и, следовательно, сделать алгоритм возведения в степень более оптимальным.
Окно фактически представляет собой основание системы счисления. Пусть w — ширина окна, то есть за один раз учитывается w знаков показателя.
Рассмотрим метод окна.
В данном алгоритме требуется k возведений в квадрат, но число умножений в среднем сокращается до k/w.
Ещё более эффективным является метод скользящего окна. Он заключается в том, что ширина окна во время выполнения процесса может изменяться:
Количество операций возведения в степень в данном алгоритме такое же, как и в методе окна, а вот количество операций умножений сократилось до l, то есть до k w + 1 {displaystyle {frac {k}{w+1}}} в среднем.
Для примера возведём методом скользящего окна число x в степень 215. Ширина окна w = 3.
Применение
Алгоритм быстрого возведения в степень получил широкое распространение в криптосистемах с открытым ключом. В частности, алгоритм применяется в протоколе RSA, схеме Эль-Гамаля и других криптографических алгоритмах.