= Exponentiation by squaring
{title2=$a^n$}
{wiki}
= Repeated squaring
{synonym}
= Fast exponentiation
{synonym}
= Binary exponentiation
{synonym}
Exponentiation by squaring computes an <integer> power by reading the exponent's <binary expansion>. Appending a <binary digit> $b$ to a prefix of value $p$ replaces $p$ by $2p+b$, so the corresponding power changes by
$$
a^{2p+b}=(a^p)^2a^b,\qquad b\in\{0,1\}.
$$
Each new digit requires one squaring and, only for digit one, one further <multiplication>. The number of digits grows with the <logarithm> of the exponent, making this useful for <modular exponentiation>, <primality testing>, and powers of <matrices> using <matrix multiplication>.<A Computational Introduction to Number Theory and Algebra by Victor Shoup>[Section 3.4, pp. 65–66: binary-prefix recurrence and repeated-squaring algorithm; p. 67: primality-testing application]{ref}
For a concrete calculation, $13=(1101)_2=8+4+1$, so $3^{13}=3^8\cdot3^4\cdot3$. The \b[optimized left-to-right <algorithm> used here] instead keeps one accumulated power: initialize $r=3$ from the leading digit one, then process only the remaining digits $1,0,1$:
$$
\begin{aligned}
1&:\quad r=3,\\
11&:\quad r=3^2\cdot3=27,\\
110&:\quad r=27^2=729,\\
1101&:\quad r=729^2\cdot3=531441\cdot3=1594323.
\end{aligned}
$$
Thus \b[$3^{13}=1594323$], using three squarings and two further <multiplications>, instead of twelve successive <multiplications> starting at $3$.
\Image[/binary-powering-prefix-and-modular-trace.png]
{title=Reading the same <binary expansion> computes $3^{13}$ and $2^{13}\bmod17$}
{description=Each appended <binary digit> changes the prefix value by $p\mapsto2p+b$. The ordinary-power row grows to $1594323$; the <modular exponentiation> row stores only remainders $2,8,13,15$. Both traces use three squarings and two further <multiplications>.}
For a general positive <integer> $n=(b_{\ell-1}\cdots b_0)_2$ with leading digit $b_{\ell-1}=1$, set $r=a$ and, for $i=\ell-2,\ldots,0$, first replace $r$ by $r^2$, then multiply it by $a$ if $b_i=1$. Return $r$. This explicitly skips the leading digit's otherwise unnecessary operations on one. <A Computational Introduction to Number Theory and Algebra by Victor Shoup> (Section 3.4, pp. 65–66) presents the version initialized at one and processing every digit; the optimization here makes the counting convention unambiguous.
The <loop invariant> is \b[$r=a^p$, where $p$ is the value of the digits already read]. Initially $p=1$ and $r=a$. If the next digit is $b$, then squaring and optionally multiplying give $r'=a^{2p+b}$, exactly the next prefix. At termination $p=n$. This proof uses <associativity> of <multiplication>; it works in any <monoid>, including <matrices> with the <identity matrix> as <identity element>, and needs no <commutativity> between different bases.
For $n=0$, return the <identity element> without performing a <multiplication>. This is the empty-product convention $a^0=1$; if $a=0$, the <algorithm> therefore returns one for $0^0$ by convention, rather than resolving its meaning in every mathematical setting. Negative <integer> exponents require an <inverse element>: compute $(a^{-1})^{-n}$, counting the inversion separately. Over the <integers>, such an inverse generally leaves the <integers>, and a zero base has no inverse.
Back to article page
