This site's Number Theory category holds fourteen entries, and unlike Comparison Sorts or Shortest Paths, most of them aren't competing answers to one question — they're a small toolbox where several later entries are built directly out of earlier ones. Three of the fourteen, Karatsuba Multiplication, Toom-Cook Multiplication, and Fast Fourier Transform, sit a layer below the rest: every other entry here counts its cost in multiplications and treats each one as a single cheap step, an assumption that stops holding once the numbers themselves run to hundreds of digits — Karatsuba and Toom-Cook speed up multiplying two such numbers directly (splitting into two and three pieces respectively), the FFT speeds up the more general problem of convolving two coefficient sequences (which the same big-number multiplication reduces to, at a large enough size). None of the three competes for "what do you have in hand" the way the eleven below do, so all three sit outside this guide's decision tree and comparison table — see their own pages for how each beats schoolbook multiplication's O(n²).
Euclidean Algorithm and Extended Euclidean Algorithm start from two
specific numbers and ask how they relate. Sieve of Eratosthenes and Miller–Rabin Primality Test both answer "is
this prime," but for input shapes so different that neither can substitute for the other. Pollard's Rho Algorithm starts from the opposite
premise — a number already known composite — and finds an actual factor instead. Modular Exponentiation answers a computation asked
of it directly — and is also the exact routine Miller–Rabin, Modular Inverse via Fermat's Little Theorem, Tonelli–Shanks, and Baby-Step Giant-Step all call internally,
reference-for-reference. The last two ask questions that sound alike — recover something Modular
Exponentiation would otherwise compute forward — but land in opposite regimes. Tonelli–Shanks recovers a modular square root
r with r² ≡ n (mod p), in polynomial time, always. Baby-Step Giant-Step recovers the exponent
x with gx ≡ h (mod p) instead, and no polynomial algorithm for
that is known — the one entry in this category whose hardness (not just its cost) is the point. Chinese Remainder Theorem answers a genuinely
different kind of question — about a whole system, not one number or pair — by calling Extended
Euclidean once per merge step. Lucas' Theorem answers yet
another shape of question — a binomial coefficient mod a prime, for an n too large to compute
factorials over directly — by decomposing into base-p digits and calling the Fermat-inverse route on
each one, small enough that it never hits the failure that route has on its own. So this guide asks
what you actually have in hand, not which algorithm sounds fastest.
If the question is just "what's the largest number that divides both a and b, with no
remainder" — nothing more — Euclidean Algorithm is
the whole answer: repeatedly replace the larger number with the remainder after dividing by the
smaller, in O(log(min(a, b))) steps, a bound its own Complexity section proves tight
against consecutive Fibonacci pairs. It looks like it should also work fine as repeated subtraction
instead of remainder — and it does, correctness-wise — but the page's own Pitfalls section measures
the gap directly: gcd(1, 1000000) takes 2 steps the remainder way and 999,999 the
subtractive way, both landing on the same correct answer.
If the question goes further — not just the gcd, but the actual integers x and
y satisfying a·x + b·y = gcd(a, b) (Bézout's identity), typically because
what's really wanted is a modular inverse — that's Extended Euclidean Algorithm: the identical
reduction loop, carrying two extra running coefficients alongside the remainder, at the same
O(log(min(a, b))) cost. It works for any modulus with gcd(a, m) = 1,
prime or not — the general-purpose route. Its own Pitfalls section flags two sharp edges worth
knowing before trusting its output blind: the returned x can come out negative and needs
folding into [0, m) by hand (JavaScript's % won't do it for you), and
x/y aren't unique — a different reduction path produces a different, equally
valid pair.
There's a second, narrower route to the same modular inverse Extended Euclidean already
provides: Modular Inverse via Fermat's Little
Theorem computes it as ap-2 mod p — one call to the same
modPow routine Modular
Exponentiation builds, no gcd reduction at all. Its own Complexity section is direct about the
trade: "neither route wins on asymptotic grounds alone... the real trade-off is scope, not speed."
The restriction is absolute, not a rare edge case — the modulus must be prime. Feed it a
composite modulus and it doesn't error, it returns a wrong number that looks exactly as legitimate as
a right one: the page's own sweep across every composite modulus from 4 to 200 found the Fermat-route
formula disagreeing with the true inverse in 93.4% of checked pairs. Reach for this shortcut only when
the modulus is known-prime and the code already has a hardened modPow sitting
around (finite-field and elliptic-curve cryptography routinely do); otherwise, Extended Euclidean's
lack of a precondition makes it the safer default.
This splits on a single question: is it every prime up to some bound, or is it one specific
candidate? Sieve of Eratosthenes finds every
prime up to a bound n in one coordinated sweep, O(n log log n) time — one of
the fastest known ways to enumerate primes up to bounds in the tens of millions, but it has to
allocate and touch an array of size n, which is exactly what makes it the wrong tool the
moment the actual question is about one number with hundreds of digits rather than a bound: its own
closing paragraph says so directly, "trial division against a sieve doesn't scale once that number has
hundreds of digits, the regime cryptography actually cares about."
For that regime — one specific, possibly huge candidate — Miller–Rabin Primality Test decides primality
in O(k log³ n) for k witnesses, polynomial in the number of digits
of n rather than in n itself. It isn't a slower, more general sieve — it's a
different algorithm entirely, built on repeated squaring via the same modPow Modular
Exponentiation defines, and it trades certainty for speed: each witness has at most a 1-in-4 chance of
being fooled by a composite number, so k independent witnesses drop the failure
probability to at most 4-k — under one in a million after 10 rounds. It
catches what a plain Fermat test can't: the page's own worked example shows 561, a Carmichael number,
passing the naive Fermat test for every base checked, with no amount of re-rolling ever exposing it —
Miller–Rabin's extra squaring step catches it anyway, on the first witness tried.
This is a different question from the two above, not a harder version of them — knowing a number
isn't prime doesn't hand you its factors. Pollard's Rho Algorithm finds one in
O(n1/4) expected modular operations, heuristically, using Floyd's tortoise-and-hare cycle detection over the
pseudorandom sequence x² + c mod n: a
birthday-paradox collision mod the unknown smallest factor p shows up as a
gcd greater than 1 long before the sequence would cycle mod n itself. It's
the one entry in the category whose bound is a heuristic rather than a proof, and the one whose core
loop can outright fail on a given try — its own Pitfalls section shows the same n = 8,051 succeeding
in 3 steps with one constant and collapsing after 14 steps with another, recoverable only by retrying
with a different constant. That trade — occasional retries, no worst-case guarantee — buys a
dramatically smaller search than trial division: for a 40-digit semiprime, n1/4
has roughly 10 digits against trial division's roughly 20.
If what's actually wanted is baseexp mod m as a value — not as a step
inside primality testing or an inverse — Modular
Exponentiation answers it directly: square-and-multiply computes it in O(log exp)
modular multiplications instead of the naive approach's O(exp), and, just as important,
never lets any intermediate value grow past mod² − 1 — its own Pitfalls section measures
the naive alternative building a 188-digit intermediate number for an input whose final answer is two
digits. This is the one entry in the category that's less a competing answer than a shared engine:
Miller–Rabin and the Fermat inverse route both call this exact routine, reference-for-reference,
rather than reimplementing their own.
If what's in hand is a prime p and a number n already known to be a square
mod p, and what's wanted is an actual square root — some r with
r² ≡ n (mod p) — Tonelli–Shanks
answers it in O(log² p), polynomial in the digits of p, always. First it checks
Euler's criterion (one modPow call) to confirm n really is a residue at all —
skipping that check doesn't make the rest of the algorithm return a wrong answer for a non-residue, its
own Pitfalls section shows, it makes the general-case loop exhaust its search range and get stuck, every
time, a structural consequence of a non-residue's order rather than an occasional edge case. Then it
splits on p mod 4: p ≡ 3 (mod 4) gets a one-line direct formula; the more common
p ≡ 1 (mod 4) case needs a real loop, and its own Pitfalls section is explicit that reaching
for the direct formula unconditionally — a shortcut more than one write-up stops at — fails silently
rather than erroring, since roughly half of all odd primes are 1 mod 4 and the formula's exponent isn't
even an integer for them.
Tonelli–Shanks and the next entry ask questions that sound alike — recover something Modular
Exponentiation would otherwise compute forward — and land in opposite regimes. Baby-Step Giant-Step is the one entry asking
for something Modular Exponentiation would normally
compute for you — the exponent x in gx ≡ h (mod p) — run in
reverse, and reversing it isn't just slower, it's the one place in this whole category where hardness
itself, not merely cost, is the entire point: no known general algorithm solves it in time polynomial in
the number of digits of p, which is exactly what makes it the basis of Diffie–Hellman and
ElGamal. Baby-step giant-step doesn't break that — it's still exponential in the bit-length of
p — but its O(√p) meet-in-the-middle search beats brute force's O(p)
by trading memory for time: precompute every gj for j up to
√p once, then check at most √p candidate values against that table instead of
walking every exponent one at a time. Its own Pitfalls section shows the sharp edge in that trade
directly: rounding the table size down by even one — ⌊√(p−1)⌋ instead of ⌈√(p−1)⌉
— silently shrinks the reachable exponent range and reports "no solution" on an input that has one, a
failure mode indistinguishable from the input genuinely having no solution at all.
Chinese Remainder Theorem is the one entry
asking a different shape of question outright: given several remainder/modulus pairs — "2 mod
3, 3 mod 5, 2 mod 7" — what single number (up to the product of the moduli) satisfies every one of
them simultaneously? It isn't new machinery: each pair of congruences merges into one via a single
call to Extended Euclidean, so n congruences collapse pairwise into one answer in
O(n log M), where M is the final combined modulus. Unlike the textbook
formula (which silently assumes every modulus is pairwise coprime), the pairwise-merge approach this
page ships generalizes past that: its own Pitfalls section verifies it against 20,000 random
congruence sets, including moduli that share a factor, and confirms it correctly reports "no solution"
— rather than guessing — when the congruences genuinely contradict each other.
If the question is C(n, k) mod p — a binomial coefficient, reduced mod a known prime
p — and n can run to hundreds of digits, Lucas' Theorem is the only entry built for it. The obvious
route (compute n!, k!, and (n−k)! mod p and
combine them with the Fermat-inverse route above) looks like a two-line reuse of machinery this guide
already covers, and works right up until k or n−k reaches
p — at which point one of those factorials contains p itself as a factor, is
congruent to 0 mod p, and has no modular inverse. Its own Pitfalls section measures
exactly how often that silent failure produces a wrong answer rather than an error: forcing k
≥ p across 30,000 trials, the naive route returned exactly 0 every time, and that 0 was
wrong 27.2% of the time against the true value. Lucas' Theorem avoids the problem entirely by
decomposing n and k into base-p digits first and multiplying
one small binomial coefficient per digit — each strictly under p, so the factorial in
that per-digit calculation never has a chance to hit a multiple of p in the first place.
It's O(p logp n), a cost that depends on p, not on how many digits
n itself has — the entire reason it exists.
Two reuse chains run through this whole category, and neither is incidental — the pages themselves
say so in their own words. Extended Euclidean
Algorithm feeds Chinese Remainder
Theorem: every congruence merge is one Extended Euclidean call. Modular Exponentiation feeds Miller–Rabin, the Fermat inverse route, Tonelli–Shanks, and Baby-Step Giant-Step's own giant-step multiplier: all
four call the identical modPow routine internally — Tonelli–Shanks for its Euler's-criterion
check, its fast-path formula, and every exponentiation in its general loop — and baby-step giant-step
reaches for Extended Euclidean too, via modInv, to invert g before the
giant-step phase can even start — the one entry in the category that pulls from both chains at once.
The Modular Exponentiation chain runs one link further still: Lucas' Theorem calls the Fermat inverse route once per
base-p digit of n and k, safely this time, since every digit it
passes in is guaranteed smaller than p — the exact precondition the Fermat inverse route's
own page requires and the naive whole-number version above breaks. Practically, that means a codebase
that already has a hardened Extended Euclidean and a hardened modPow is most of the way to
every other entry in this category — Chinese Remainder Theorem, the Fermat shortcut, Tonelli–Shanks,
baby-step giant-step, and Lucas' Theorem aren't separate algorithms to learn from scratch so much as new
ways to call routines already on hand.
| Entry | Answers | Complexity | Reach for it when |
|---|---|---|---|
| Euclidean Algorithm | gcd(a, b) | O(log(min(a, b))) | only the divisor itself is needed, not a combination producing it |
| Extended Euclidean Algorithm | gcd(a, b) plus Bézout coefficients x, y | O(log(min(a, b))) | a modular inverse or Bézout combination is needed, for any modulus |
| Sieve of Eratosthenes | every prime up to a bound n | O(n log log n) | the bound n is reachable in memory (up to the tens of millions) |
| Miller–Rabin Primality Test | is one specific n prime, probabilistically | O(k log³ n) | n is one candidate, possibly hundreds of digits long |
| Pollard's Rho Algorithm | a nontrivial factor of a known-composite n | O(n1/4) expected | n is known composite and an actual divisor is needed, not just a primality verdict |
| Modular Exponentiation | baseexp mod m | O(log exp) multiplications | the exponentiation itself is the answer, or another routine needs it |
| Modular Inverse via Fermat's Little Theorem | the modular inverse of a mod p | O(log p) multiplications | p is known prime and a hardened modPow is already on hand |
| Tonelli–Shanks Algorithm | r with r² ≡ n (mod p) | O(log² p) expected | a modular square root needs recovering, and n is already confirmed a residue |
| Chinese Remainder Theorem | one x satisfying several congruences at once | O(n log M) | several remainder/modulus pairs need combining into one number |
| Baby-Step Giant-Step | the exponent x with g^x ≡ h (mod p) | O(√p) time and space | a discrete logarithm needs recovering, not just computing g^x forward |
| Lucas' Theorem | C(n, k) mod p | O(p logp n) | a binomial coefficient is needed mod a small prime and n is too large for exact factorials |