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

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

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

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

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

ОписаниеПравить

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

Пусть

$n=(\stackrel{¯<!--\; ¯\; -->}{m_k{m}_{k-<!--\; -\; -->1}...m_1{m}_0}{)}_2$$n=(\overline {m_{{k}}m_{{k-1}}...m_{{1}}m_{{0}}})_{2}$  — двоичное представление степени n, то есть,

$n=m_k\cdot <!--\; \cdot \; -->2^k+m_{k-<!--\; -\; -->1}\cdot <!--\; \cdot \; -->2^{k-<!--\; -\; -->1}+\cdots <!--\; \cdots \; -->+m_1\cdot <!--\; \cdot \; -->2+m_0,$$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\in <!--\; \in \; -->\{0,1\}$$m_{{k}}=1,m_{{i}}\in \{0,1\}$ . Тогда

$x^n=x^{((\dots <!--\; \dots \; -->((m_k\cdot <!--\; \cdot \; -->2+m_{k-<!--\; -\; -->1})\cdot <!--\; \cdot \; -->2+m_{k-<!--\; -\; -->2})\cdot <!--\; \cdot \; -->2+\dots <!--\; \dots \; -->)\cdot <!--\; \cdot \; -->2+m_1)\cdot <!--\; \cdot \; -->2+m_0}=((\dots <!--\; \dots \; -->(((x^{m_k}{)}^2\cdot <!--\; \cdot \; -->x^{m_{k-<!--\; -\; -->1}}{)}^2\dots <!--\; \dots \; -->{)}^2\cdot <!--\; \cdot \; -->x^{m_1}{)}^2\cdot <!--\; \cdot \; -->x^{m_0}$$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. Если $m_i$$m_i$  = 1, то текущий результат возводится в квадрат и затем умножается на x. Если $m_i$$m_i$  = 0, то текущий результат просто возводится в квадрат. Индекс i изменяется от k-1 до 0.

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

$\left\{\begin{array}{c}{s}_1=x\\ s_{i+1}=s_i^2\cdot <!--\; \cdot \; -->x^{m_{k-<!--\; -\; -->i}}\\ i=1,2,\dots <!--\; \dots \; -->,k\end{array}\right\}.$${\begin{Bmatrix}s_{1}=x\\s_{{i+1}}=s_{i}^{2}\cdot x^{{m_{{k-i}}}}\\i=1,2,\dots ,k\end{Bmatrix}}.$ 

ОбобщенияПравить

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

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

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

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

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

${13}_{10}={1101}_2$$13_{10}=1101_{2}$ 

$m_3=1,m_2=1,m_1=0,m_0=1$$m_{3}=1,m_{2}=1,m_{1}=0,m_{0}=1$ 

${\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. Если $m_i=1$$m_{i}=1$ , то текущий результат умножается на z, а само число z возводится в квадрат. Если $m_i$$m_i$  = 0, то требуется только возвести z в квадрат. При этом индекс i, в отличие от схемы слева направо, изменяется от 0 до k-1 включительно.

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

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

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

$=a^{\underset{i=0}{\overset{k}{\sum <!--\; \sum \; -->}}{m}_i\cdot <!--\; \cdot \; -->2^i}=$$= a^{\sum_{i=0}^k m_i\cdot 2^i} =$ 

$=a^{m_0}\cdot <!--\; \cdot \; -->a^{2m_1}\cdot <!--\; \cdot \; -->a^{2^2\ast <!--\; \ast \; -->m_2}\cdot <!--\; \cdot \; -->...\cdot <!--\; \cdot \; -->a^{2^k\ast <!--\; \ast \; -->m_k}=$$= a^{m_0}\cdot a^{2m_1}\cdot a^{2^2*m_2}\cdot ... \cdot a^{2^k*m_k}=$ 

$=a^{m_0}\cdot <!--\; \cdot \; -->(a^2{)}^{m_1}\cdot <!--\; \cdot \; -->(a^{2^2}{)}^{m_2}\cdot <!--\; \cdot \; -->...\cdot <!--\; \cdot \; -->(a^{2^k}{)}^{m_k}=$$= a^{m_0}\cdot (a^2)^{m_1}\cdot (a^{2^2})^{m_2}\cdot ... \cdot (a^{2^k})^{m_k}=$ 

$=\underset{i=0}{\overset{k}{\prod <!--\; \prod \; -->}}(a^{2^i}{)}^{m_i}$$=\prod _{{i=0}}^{k}{(a^{{2^{{i}}}})^{{m_{i}}}}$ .

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

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

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

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

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

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

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

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

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

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

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

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

Количество операций возведения в степень в данном алгоритме такое же, как и в методе окна, а вот количество операций умножений сократилось до l, то есть до $\frac{k}{w+1}$$\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. — С. 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