Introduction to Exponentiation by Squaring

Many computations boil down to combining a single value with itself \(n\) times: adding a number to itself to multiply, multiplying a number by itself to exponentiate, or applying a function to its own output to iterate it. Done one step at a time, all of these cost \(n\) operations. Halving \(n\) while doubling the thing being combined turns every one of them into roughly \(\log_2 n\) operations instead, and the same halving-and-doubling argument is what makes fast modular exponentiation, matrix-based Fibonacci, and binary lifting on trees all work for the same underlying reason.

Old Multiplication by Halving and Doubling

Take the schoolbook definition of multiplication as repeated addition, \(a\cdot b=\underbrace{b+b+\dots+b}_{a\text{ times}}\), and write \(a\) in binary, \(a=\sum_{i=0}^{k}a_i 2^i\) with each \(a_i\in\{0,1\}\). Substituting this into the sum of \(b\)'s and grouping by power of two gives

\[ a\cdot b = \sum_{i=0}^{k} a_i\left(2^i b\right) = \sum_{i:\,a_i=1} 2^i b. \]

Only the powers of two that actually appear in \(a\)'s binary expansion contribute, and each term \(2^i b\) is just the previous term doubled: \(2^{i+1}b=2^ib+2^ib\). The bits \(a_i\) themselves fall out of \(a\) by the same repeated halving: \(a_0\) is the remainder of \(a\) divided by \(2\), and the next bit is the same test applied to \(\lfloor a/2\rfloor\). Halving \(a\) and doubling \(b\) in lockstep therefore produces exactly the terms the sum needs, in exactly the order the halving reveals them:

\[ \begin{array}{rl} \text{start:} & a_0=a,\ b_0=b,\ r=0\\ \text{step:} & \text{if }a_i\text{ is odd, } r \mathrel{+}= b_i;\quad a_{i+1}=\lfloor a_i/2\rfloor,\ b_{i+1}=2b_i\\ \text{stop:} & \text{once }a_i=0,\ r=a\cdot b. \end{array} \]

This is the old "peasant multiplication": halve one column, double the other, and add up the doubled column wherever the halved column is odd. For \(12\cdot14\):

Summing the marked rows gives \(56+112=168=12\cdot14\), matching ordinary multiplication while never using anything but halving, doubling, and addition.

From Doubling to Squaring: Ordinary Exponentiation

Nothing in the argument above actually depends on addition. Relabel it: replace the accumulated operation \(+\) by \(\times\), its identity element \(0\) by \(1\), and "doubling" \(b\mathrel{+}=b\) by "squaring" \(x\mathrel{*}=x\). The same halving-of-the-exponent argument, applied to \(x^n=\underbrace{x\cdot x\cdots x}_{n\text{ times}}\) instead of \(a\cdot b\), gives

\[ x^n = \prod_{i:\,n_i=1} x^{2^i}, \]

built by squaring \(x\) at every step and multiplying it into the result whenever the current bit of \(n\) is \(1\). For \(x^{13}\), since \(13=8+4+1\) in binary:

giving \(x^1\cdot x^4\cdot x^8=x^{13}\). Put side by side, the two algorithms are the same loop with two symbols swapped:

function mul(p, n) {           function pow(x, n) {
    let r = 0;                     let r = 1;
    while (n > 0) {                 while (n > 0) {
        if (n & 1) r += p;             if (n & 1) r *= x;
        p += p;                         x *= x;
        n >>= 1;                        n >>= 1;
    }                               }
    return r;                       return r;
}                               }

Modular Exponentiation

Cryptographic uses of exponentiation, such as RSA and Diffie–Hellman, need \(x^n\bmod m\) for numbers with hundreds of digits, where \(x^n\) itself would be astronomically larger than \(m\) long before the exponentiation finished. What makes the squaring trick work here as well is that reduction modulo \(m\) is compatible with multiplication: writing \(a=q_1m+r_1\) and \(b=q_2m+r_2\),

\[ ab = q_1q_2m^2+q_1r_2m+q_2r_1m+r_1r_2 \equiv r_1r_2 \pmod m, \]

since every other term carries a factor of \(m\). In other words \((ab)\bmod m=\big((a\bmod m)(b\bmod m)\big)\bmod m\), so reducing modulo \(m\) after every squaring and every multiplication in the algorithm above never changes the final answer, and it keeps every intermediate value below \(m^2\) instead of letting it grow with \(n\).

For \(7^{29}\bmod17\), write \(29=16+8+4+1\) in binary and build the repeated squares of the base modulo \(17\):

\[ \begin{array}{rl} 7^1 \bmod 17 &= 7\\ 7^2 \bmod 17 &= 49 \bmod 17 = 15\\ 7^4 \bmod 17 &= 15^2 \bmod 17 = 225 \bmod 17 = 4\\ 7^8 \bmod 17 &= 4^2 \bmod 17 = 16\\ 7^{16}\bmod 17 &= 16^2 \bmod 17 = 256 \bmod 17 = 1 \end{array} \]

and multiply together the rows matching the set bits of \(29\):

\[ 7^{29}\bmod17 = \left(7^{16}\cdot7^8\cdot7^4\cdot7^1\right)\bmod17 = (1\cdot16\cdot4\cdot7)\bmod17 = 448\bmod17 = 6. \]

None of the intermediate numbers ever exceeded \(16^2=256\), even though a naive computation of \(7^{29}\) itself would already have 25 digits.

function modpow(b, e, m) {
    let r = 1;
    b = b % m;
    while (e > 0) {
        if (e & 1) r = (r * b) % m;
        b = (b * b) % m;
        e >>= 1;
    }
    return r;
}

Complexity

Each pass through the loop halves the exponent, so the loop runs \(\lfloor\log_2n\rfloor+1\) times regardless of how large \(n\) is, performing at most one squaring and one multiplication per bit. That is \(O(\log n)\) operations in total, against the \(O(n)\) operations a direct repeated-multiplication loop would need; for the 2048-bit exponents used in real RSA keys, this is the difference between roughly \(2000\) multiplications and roughly \(2^{2048}\) of them.

The General Pattern: Exponentiating in Any Monoid

Neither derivation above used anything specific to numbers. All that was needed is a binary operation \(\ast\) that is associative and has an identity element \(e\), so that "the same thing combined with itself \(n\) times" is well defined; algebraically, this is a monoid. Applying the halving-and-doubling argument to any such \((\ast,e)\) gives, for a fixed element \(x\),

\[ x^{\ast n} = \bigotimes_{i:\,n_i=1} x^{\ast 2^i}, \qquad x^{\ast 2^{i+1}} = x^{\ast 2^i}\ast x^{\ast 2^i}, \]

computed with \(O(\log n)\) applications of \(\ast\). The operation does not need to be commutative for this to work: every term being combined is some power \(x^{\ast k}\) of the same fixed element \(x\), and powers of a single element always commute with each other, \(x^{\ast i}\ast x^{\ast j}=x^{\ast(i+j)}=x^{\ast j}\ast x^{\ast i}\), even inside a monoid, like matrices under multiplication or functions under composition, where two arbitrary elements would not commute. This is exactly why the same trick applies unchanged to the non-commutative examples below.

Application: Matrix Exponentiation and Fast Fibonacci

The Fibonacci recurrence \(F(n+1)=F(n)+F(n-1)\) can be written as a single matrix step,

\[ \begin{pmatrix}F(n+1)\\F(n)\end{pmatrix} = \begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}F(n)\\F(n-1)\end{pmatrix}, \]

so starting from \(\begin{pmatrix}F(1)\\F(0)\end{pmatrix}=\begin{pmatrix}1\\0\end{pmatrix}\), applying this step \(n\) times gives \(\begin{pmatrix}F(n+1)\\F(n)\end{pmatrix}=M^n\begin{pmatrix}1\\0\end{pmatrix}\) with \(M=\begin{pmatrix}1&1\\1&0\end{pmatrix}\). Matrix multiplication is associative with the identity matrix as its identity element, so \(M^n\) is computed by squaring the matrix \(O(\log n)\) times instead of multiplying \(n\) copies of it together, turning Fibonacci computation from \(O(n)\) additions into \(O(\log n)\) \(2\times2\) matrix multiplications.

Application: Binary Lifting on Functional Graphs

Let \(f:V\to V\) be a function on some finite set, such as the parent pointer of a node in a tree. Function composition is associative with the identity function as its identity element, so the \(n\)-fold application \(f^{\circ n}=f\circ f\circ\dots\circ f\) is again an exponentiation in this monoid. Precomputing the doubling steps once, as a table \(\text{jump}[0][v]=f(v)\) and \(\text{jump}[k][v]=\text{jump}[k-1]\big(\text{jump}[k-1][v]\big)\), lets any single query \(f^{\circ n}(x)\) be answered in \(O(\log n)\) by combining the precomputed jumps according to the bits of \(n\), exactly as the exponent's bits selected which squared values to multiply in above. This technique, known as binary lifting, is the standard way to answer "\(k\)-th ancestor of a node" and lowest-common-ancestor queries on trees in \(O(\log n)\) after \(O(n\log n)\) preprocessing.

Application: Repeating a String

String concatenation is associative with the empty string as its identity element, and while concatenation is not commutative in general, copies of one fixed string \(p\) commute with each other for the same reason powers of a fixed matrix or function do. Repeating \(p\) \(n\) times is therefore another exponentiation, computed by doubling the string instead of appending one copy of \(p\) at a time:

function repeat(p, n) {
    let r = "";
    while (n > 0) {
        if (n & 1) r += p;
        p += p;
        n >>= 1;
    }
    return r;
}

Applications at a Glance

Common Pitfalls

• The operation must be associative for "combined with itself \(n\) times" to even be well defined; subtraction and division, for instance, are not associative and cannot be exponentiated this way.
• In the modular case, forgetting to reduce the accumulator \(r\), not just the squared base \(b\), after every multiplication lets it grow back toward the size of the un-reduced result.
• The commuting argument only covers powers of the same fixed element; it does not make the underlying monoid commutative, so two different matrices or two different functions still cannot be swapped in general.
• \(n=0\) must return the identity element directly, since the loop body is never entered; omitting this case silently breaks callers that legitimately ask for the zeroth power.

Key Results

• Writing the exponent \(n\) in binary and halving it while doubling (or squaring) the base turns \(n\) sequential combinations into \(O(\log n)\) of them.
• Ordinary exponentiation, modular exponentiation, matrix exponentiation, binary lifting on functions, and string repetition are all the same algorithm, differing only in which associative operation and identity element are substituted in.
• Modular exponentiation is correct because reduction modulo \(m\) commutes with multiplication, \((ab)\bmod m=((a\bmod m)(b\bmod m))\bmod m\), which also keeps every intermediate value bounded by \(m^2\).
• The technique needs the combined operation to be associative but not commutative, since all the terms it ever combines are powers of one fixed element, and those always commute with each other.
• The same \(O(\log n)\) argument is what makes 2048-bit RSA exponentiation, \(O(\log n)\) Fibonacci via matrix powers, and \(O(\log n)\) ancestor queries via binary lifting all practical.