The site's fifth Number Theory entry. The question: given base,
exp, and mod, what is baseexp mod mod — without ever
forming the full, possibly astronomical, number baseexp along the way? This isn't a
new idea on this site: Miller–Rabin already
leans on it, compressed into one small modPow helper, to test whether a number with hundreds of
digits is prime. This page unpacks exactly what that helper does and why it stays fast and small no matter
how large exp gets.
The naive approach — multiply base by itself exp times, then reduce mod
mod once at the end — costs exp multiplications and, worse, lets the intermediate
number grow without bound the whole way (see Pitfalls). Square-and-multiply
does both better: reduce mod mod after every multiplication, and reuse each squared
value for two bits' worth of work at once, cutting the multiplication count from exp down to
about log₂(exp).
Enter a base, exponent, and modulus, then step through the exponentiation one bit at a time. 3, 13, 7 is small enough to check by hand. The other two presets replay numbers from Miller–Rabin's own Pitfalls section — this is the exact computation that decides whether witness 2 or witness 3 exposes 2047 as composite.
Write the exponent in binary: exp = b0 + b1·2 + b2·4 + ...
with each bi either 0 or 1. Then
base^exp = base^(b0 + 2b1 + 4b2 + ...) = (base^1)^b0 · (base^2)^b1 · (base^4)^b2 · ...Each factor base2i is just the previous one squared, so the whole
sequence — base1, base2, base4, base8, ... — costs
one squaring per step to build, no matter how large exp is. The algorithm walks
exp's bits from least significant to most significant: at bit i, it already has
base2i mod mod sitting in a running variable; if that bit is 1 it multiplies
that value into the running result, then squares it (mod mod) to get ready for bit
i + 1, and shifts the exponent right to expose the next bit. Reducing mod mod after
every squaring and every multiply keeps every number the algorithm ever holds below
mod² — the size of exp only affects how many bits there are to walk, never how big
any single number gets.
function modPow(base, exp, mod) { // all BigInt; exp assumed >= 0
base = ((base % mod) + mod) % mod;
let result = 1n % mod;
while (exp > 0n) {
if (exp & 1n) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1n;
}
return result;
}This is the same routine, reference-for-reference, that Miller–Rabin's own modPow uses
internally — the only difference is the 1n % mod starting point instead of a bare
1n, which matters only for the mod = 1 edge case below (Miller–Rabin never
calls it with a modulus that small, so its version never needed the extra care).
Scanning the exponent's bits in the wrong order doesn't crash — it silently computes a
different power. The algorithm above is built around one specific pairing: process bits
least-significant-first, and square the base after using it. Flip that to scan the bits
most-significant-first while keeping the same "multiply-then-square" step, and the running base no
longer lines up with the bit it's paired against. Toggle the checkbox above on the default preset
(3, 13, 7, where 13 is 1101 in binary — not a palindrome, so the bug is
visible without changing any input) and the answer changes from the correct 3 to
5. That's not noise: 5 is the exact answer to 311 mod 7, and 11 is
1011 — the bit-reversal of 13's 1101. This was checked, not just observed once:
sweeping every base in [1, 15], exp in [0, 63], and mod in [2, 15]
(13,440 combinations), the broken scan's output matched base^reverseBits(exp) mod mod exactly
every time, and diverged from the true, correctly-ordered answer in 4,067 of those 13,440 cases — whenever
the exponent's binary form isn't its own reversal.
Reducing mod mod only once, at the very end, isn't just slower — the intermediate
number it builds can dwarf the final answer by orders of magnitude. Take base = 7,
exp = 222, mod = 13: the correct answer is 12. Computing
7222 in full before reducing requires building and holding a
188-digit integer, checked directly by running the multiplication out. Reducing mod 13 after
every squaring, as the reference implementation does, never lets any intermediate value exceed
mod² − 1 = 168 — a three-digit number, for the exact same computation. The gap only widens as
exp grows: real uses of this algorithm (RSA key generation, Diffie–Hellman, and
Miller–Rabin itself) routinely run it with exponents hundreds of digits long, where the
never-reduce-until-the-end version isn't just slow, it's computationally out of reach.
An unreduced starting result is invisible for almost every input — except mod = 1.
Initialize result to a bare 1n instead of 1n % mod, and for
any exponent with at least one set bit, the loop's own % mod on the first multiply
corrects it before it's ever observed — checked: modPow(5, 7, 1) comes out 0
either way, since the bug is masked the moment a real multiply happens. The one case that exposes it is
exp = 0, where the loop body never runs at all: modPow(5, 0, 1) is mathematically
0 (everything reduces to 0 modulo 1, including the base case), but the unreduced version
returns the bare starting 1 instead — checked directly, and the only input shape in this
whole algorithm where that particular oversight actually surfaces.
O(log exp) modular multiplications — one squaring per bit of exp, plus at
most one extra multiply per set bit — against the naive approach's O(exp) multiplications. Each
individual multiplication is on numbers bounded by mod², regardless of how large
exp is, which is exactly what makes this usable with exponents that have hundreds of digits.
Extended Euclidean Algorithm already computes
a modular inverse a different way, via Bézout coefficients, for any modulus; when the modulus happens to be
prime, Fermat's Little Theorem gives a second
route straight through this page's own routine — amod − 2 mod mod is
a's inverse.
This site's guide, Choosing a Number Theory Algorithm, compares this entry against the other thirteen Number Theory entries side by side.