Fast Modular Exponentiation

Public-key cryptography rests on computing things like m^{e} \bmod n where the exponent e has hundreds of digits. Multiplying m by itself e times would take longer than the age of the universe. The square-and-multiply method does it in a flash — and it is the reason modern cryptography is practical at all.

The trick: square, don't multiply

Repeatedly squaring reaches enormous exponents in very few steps, because each squaring doubles the exponent:

m \to m^2 \to m^4 \to m^8 \to m^{16} \to \cdots

After k squarings you have m^{2^k}. Reaching exponent 2^{1000} needs only 1000 squarings, not 2^{1000} multiplications — and crucially, you reduce mod n after every step, so the numbers never grow large.

Filling in any exponent with binary

Any exponent is a sum of powers of two — its binary expansion. So m^e is the product of the squarings whose bit is 1. For 13 = 1101_2 = 8 + 4 + 1:

m^{13} = m^{8} \cdot m^{4} \cdot m^{1}.

So computing 7^{13} \bmod 11 takes a handful of operations:

7^1\equiv 7,\ \ 7^2\equiv 5,\ \ 7^4\equiv 5^2 = 25\equiv 3,\ \ 7^8\equiv 3^2 = 9 \pmod{11}

7^{13} \equiv 9 \cdot 3 \cdot 7 = 189 \equiv 2 \pmod{11}.

How fast is it?

An exponent e needs only about \log_2 e squarings and at most that many multiplications — a logarithmic number of steps. A 2048-bit exponent takes a few thousand modular multiplications, done in milliseconds. This single efficient algorithm is what makes Fermat's theorem, Diffie–Hellman, RSA and primality testing all run in practice.