Modular Exponentiation & Primality

The previous lesson built the arithmetic of ${\mathbb{Z}}_m$: addition, multiplication, and the modular inverse via the extended Euclidean algorithm. One operation it left on the table is exponentiation: given $a$, $n$, and a modulus $m$, compute $a^n\mathrm{mod}m$. The obvious loop multiplies $a$ into an accumulator $n$ times, which is $\Theta (n)$, hopelessly slow when $n$ is a 1024-bit number, as it routinely is in cryptography. This lesson's first result is that we can do it in $O(\log n)$ multiplications. That single trick, repeated squaring, is the engine behind primality testing, the modular inverse, and the public-key primitives that secure the internet.

Binary exponentiation: repeated squaring

The idea is to read $n$ in binary. Write $n={\sum }_i{b}_i{2}^i$ with $b_i\in \{0,1\}$. Then

The numbers $a^{2^i}$ are just the repeated squares of $a$: each one is the square of the previous, since $a^{2^{i+1}}=(a^{2^i}{)}^2$. So we sweep the bits of $n$ from least to most significant, keeping a running square $a^{2^i}$, and whenever the current bit is $1$ we multiply that square into the result.

Each square is one multiplication and there are $\lfloor {\log }_{2}n\rfloor +1$ of them; each bit costs at most one more multiplication into the accumulator. So the total is at most $2\lfloor {\log }_{2}n\rfloor +O(1)$ multiplications, which is $O(\log n)$.¹ Reducing modulo $m$ after every multiplication keeps every intermediate value below $m^2$.

Running this on $3^{13}\mathrm{mod}7$ makes the bit-scan concrete: the running square is $3,2,4,2$ across the bits of $13=1101_2$, and the accumulator picks up a factor at each set bit, finishing at $3$.

The same computation has a clean recursive shape, splitting the exponent in half:

The recursion descends by halving the exponent and rebuilds the answer on the way back up: each return squares the child's value, and an odd exponent multiplies one extra copy of $a$. For $a^{13}$ the four downward halvings $13\to 6\to 3\to 1\to 0$ unwind into four squarings, three of them carrying the extra $\cdot a$ from an odd level.

The doubling structure is not special to integers. Replace multiply with matrix multiply and the identity $[\begin{array}{cc}1& 1\\ 1& 0\end{array}{]}^n=[\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}]$ gives the $n$-th Fibonacci number in $O(\log n)$ matrix multiplications by the very same repeated-squaring loop.

Fermat's little theorem

Repeated squaring lets us compute large powers; number theory tells us what those powers are modulo a prime.

A corollary recovers the modular inverse from the previous lesson without the extended Euclidean algorithm: multiplying $a^{p-1}\equiv 1$ by $a^{-1}$ gives

a single $\text{ModPow}$ call. This only works for a prime modulus, but that is exactly the common case in competitive programming, where arithmetic is done modulo a fixed prime such as $10^9+7$.² For a general modulus, Euler's theorem generalizes Fermat: if $\gcd (a,m)=1$ then $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$, where $\phi$ is Euler's totient, giving $a^{-1}\equiv a^{\phi (m)-1}$.

Primality testing

How do we decide whether a number $n$ is prime? Three approaches, in increasing power.

Trial division — $O(\sqrt{n})$

If $n$ has a nontrivial factor it has one no larger than $\sqrt{n}$ (factors come in pairs $d\cdot (n/d)$, and the smaller is $\le \sqrt{n}$). So testing every candidate divisor up to $\lfloor \sqrt{n}\rfloor$ settles the question.

This is perfectly adequate for one moderate number (say $n\le 10^{14}$), and is the right tool when a problem hands you a single value. It is hopeless for a 200-digit cryptographic number, where $\sqrt{n}$ is astronomically large.

The Fermat test — probabilistic

Fermat's little theorem runs in reverse as a compositeness detector. If $n$ is prime, then $a^{n-1}\equiv 1(\mathrm{mod}n)$ for every $a$ coprime to $n$. So if we find a single witness $a$ with $a^{n-1}\not\equiv 1(\mathrm{mod}n)$, then $n$ is certainly composite, and one $\text{ModPow}$ call refutes primality. If instead $a^{n-1}\equiv 1$, then $n$ is only probably prime; repeat with several random $a$ to raise confidence.

The fatal caveat is the Carmichael numbers, composites such as $561=3\cdot 11\cdot 17$ for which $a^{n-1}\equiv 1(\mathrm{mod}n)$ holds for every $a$ coprime to $n$. No choice of coprime witness ever exposes them, so the Fermat test silently declares them prime. There are infinitely many. We need a test that looks deeper.

Watching the full square-root chain for $561$ shows exactly what the Fermat test misses. With witness $a=2$ and $560=2^4\cdot 35$, the chain ends at $1$ — so Fermat, which sees only that last entry, is fooled — yet it reaches $1$ from $67$, a value that is neither $+1$ nor $-1$. A prime can never square a non-$\pm 1$ residue to $1$, so that one extra observation convicts $561$ as composite.

Miller–Rabin

Miller–Rabin strengthens the Fermat test by exploiting a second fact about primes: in ${\mathbb{Z}}_p$, the only square roots of $1$ are $\pm 1$. Write the even number $n-1$ as

For a witness $a$, consider the chain obtained by computing $a^d\mathrm{mod}n$ and then squaring it $s$ times:

If $n$ is prime, this chain must end at $1$ (Fermat), and the first time it reaches $1$ it must arrive from $-1$, because $1$ has no square root other than $\pm 1$. So a prime forces one of two patterns: either $a^d\equiv 1$, or some $a^{2^{r}d}\equiv -1$ for $0\le r<s$. If neither holds, we have found a $2^{r}d$-step value that is a nontrivial square root of $1$ (it squares to $1$ but is not $\pm 1$), which a prime can never have, so $a$ is a witness that $n$ is composite.³

With random witnesses, each composite $n$ is exposed by at least three quarters of the possible $a$, so $k$ independent rounds leave a false-:qprime probability below $4^{-k}$, and crucially, Carmichael numbers are not immune, because the square-root test sees structure the Fermat test cannot. Better still, the test can be made deterministic for bounded inputs: there is a fixed small set of bases that never errs below a threshold. Testing against the first twelve primes $\{2,3,5,7,11,13,17,19,23,29,31,37\}$ is a proven-correct deterministic primality test for all $n<3.3\times 10^{24}$, covering every 64-bit (indeed every 80-bit) integer with a dozen $\text{ModPow}$ calls.⁴

Miller–Rabin decides whether $n$ is prime but never produces a factor. Factoring a large composite is a separate, much harder problem; Pollard's rho finds a nontrivial factor in expected $O(n^{1/4})$ time using a cycle-detection trick on $x\mapsto x^2+c\mathrm{mod}n$, and is the standard tool for splitting numbers too big for trial division. (The next lesson handles factoring small numbers wholesale with a sieve.)

Why this matters: cryptography

These two ingredients, fast modular exponentiation and fast primality testing, are the beating heart of public-key cryptography. RSA picks two large random primes (found by Miller–Rabin), and both encryption and decryption are a single modular exponentiation $m\mapsto m^e\mathrm{mod}N$. Diffie–Hellman key exchange computes $g^x\mathrm{mod}p$ the same way. In every case the security rests on a power being easy to compute but its inverse (factoring $N$, or the discrete logarithm) being infeasible, and $\text{ModPow}$ is what makes the easy direction $O(\log n)$.

Takeaways

• Binary exponentiation computes $a^n\mathrm{mod}m$ in $O(\log n)$ multiplications by repeated squaring, reading the bits of $n$ and multiplying in each square whose bit is $1$; reduce mod $m$ every step, and guard against overflow with 128-bit or $\text{MulMod}$ arithmetic. The same doubling gives $O(\log n)$ Fibonacci via matrix powers.
• Fermat's little theorem ($a^{p-1}\equiv 1(\mathrm{mod}p)$) gives the modular inverse $a^{-1}\equiv a^{p-2}$ for a prime modulus; Euler's theorem generalizes it to $a^{\phi (m)}\equiv 1$ for any coprime $a$.
• Trial division tests divisors up to $\sqrt{n}$ in $O(\sqrt{n})$ time, deterministic, fine for one moderate number.
• The Fermat test detects composites probabilistically but is fooled by Carmichael numbers for every coprime witness.
• Miller–Rabin writes $n-1=2^{s}d$ and watches the square-root chain $a^d,a^{2d},\dots$ collapse to $1$, catching the nontrivial square roots that betray a composite; it is probabilistic with random witnesses and deterministic below $3.3\times 10^{24}$ with the first twelve primes as bases.
• Modular exponentiation and primality testing power RSA and Diffie–Hellman; Pollard's rho handles factoring of large numbers when a factor is actually needed.