Швидке піднесення до степеня

Нехай ${\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}}.}$

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

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

Розглянемо обчислення ${\displaystyle 3^{13}}$. Двійкове представлення 13 — ${\displaystyle {(1101)}_{2}}$, отже ${\displaystyle 8+4+1=13}$.

${\displaystyle 3^{1}}$	${\displaystyle 3}$
${\displaystyle 3^{2}}$	${\displaystyle 9=3\times 3}$
${\displaystyle 3^{4}}$	${\displaystyle 81=9\times 9}$
${\displaystyle 3^{8}}$	${\displaystyle 6561=81\times 81}$

Для обчислення кожного наступного рядка потрібне одне множення.

${\displaystyle 3^{1}\times 3^{4}\times 3^{8}=3^{13}=1594323}$

Кількість множень, необхідна для піднесення числа x до степеня n алгоритмом, отримується за формулою: ${\displaystyle H+2(E-1)}$, де H — кількість нулів, а E — кількість одиниць в двійковому записі числа n. Таким чином, кількість множень дорівнює ${\displaystyle O(\log {n})}$.

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

Нехай пара (S, *) — напівгрупа, тобто є S — довільна множина, на якій завдана двомісна операція * така, що:

• Для будь-яких елементів a і b з S справедливо: (a * b) так же з S. (замкнутість)
• Для будь-яких елементів a, b і c з S справедливо: ((a * b) * c) = (a * (b * c)). (асоціативність)

Ми можемо назвати операцію * множенням і визначити піднесення до натурального степеня:

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

Для обчислення значень aⁿ можна використовувати алгоритм повторюваного піднесення до квадрата.

• Repeated Squaring (англ.)