Why number theory belongs in this rung
The previous three guides lived in the plane — orientation tests, convex hulls, the sweep line. This guide leaves geometry for arithmetic, but the spirit is identical: take an operation that looks like it must cost a lot, and find structure that makes it cheap. The two operations here are computing the greatest common divisor (GCD) of two integers, and computing a^e mod m — a base raised to a huge exponent, reduced modulo m. Both sound innocent, but they are the beating heart of RSA and almost every public-key scheme, so getting them genuinely fast and provably correct is not academic.
There is a crucial honesty point up front. When we measure these algorithms we count the input by its number of digits, not its numeric value. A number m around a thousand bits is astronomically large — far more than 2^1000 — yet its input size is only about 1000. An algorithm that ran in time proportional to m itself would be hopeless; it would be exponential in the input length. Everything below is fast precisely because it runs in time polynomial in the number of digits, which for these problems means roughly O(log of the numbers). Confusing the value of a number with the size of its description is the single most common trap in this corner of the subject.
Euclid's algorithm: shrink by remainders
The GCD of a and b is the largest integer dividing both. The naive method — try every candidate down from min(a, b) — costs time proportional to the value of the numbers, which we just saw is exponential in their size. Euclid's idea, over two thousand years old, is one line: gcd(a, b) = gcd(b, a mod b), repeated until the second argument hits 0, at which point the first argument is the answer. Why is it allowed to replace a by a mod b? Because any common divisor of a and b also divides a mod b = a - (a div b) * b, and conversely; the set of common divisors is unchanged by the swap, so the largest one is too. The GCD is an invariant of the loop, even as the numbers shrink.
Why is it fast? Watch a trace of gcd(48, 30): 48 mod 30 = 18, so gcd(30, 18); 30 mod 18 = 12, so gcd(18, 12); 18 mod 12 = 6, so gcd(12, 6); 12 mod 6 = 0, so gcd(6, 0) = 6. Each step the remainder drops, but the deeper fact is that two consecutive steps at least halve the larger number: if b <= a, then a mod b < b, and a mod b < a/2 as well (either b <= a/2, or b > a/2 and then a mod b = a - b < a/2). Halving the number every two steps means O(log a) steps total — the same logarithmic shrinkage that makes binary search fast, arrived at by a completely different route.
Extended Euclid: get the coefficients too
Plain Euclid tells you what the GCD is; the extended Euclidean algorithm also tells you how to build it from a and b. It returns not just g = gcd(a, b) but two integers x and y solving Bezout's identity: a*x + b*y = g. The trick is to carry the coefficients back up the recursion. At the base case gcd(g, 0) = g we can write g = 1*g + 0*0. Then at each return, if the deeper call gave coefficients (x', y') for gcd(b, a mod b), a little algebra rewrites them into coefficients (y', x' - (a div b)*y') for gcd(a, b). One pass down, one pass up — still O(log a) steps.
Why care about x and y? Because they hand you the modular inverse, the operation that makes modular arithmetic feel like ordinary fractions. When gcd(a, m) = 1, extended Euclid produces x and y with a*x + m*y = 1. Read that modulo m: the m*y term vanishes, leaving a*x = 1 (mod m). So x is the multiplicative inverse of a modulo m — the number you multiply by to "divide by a" inside arithmetic mod m. No inverse exists unless gcd(a, m) = 1, and extended Euclid both detects that condition (it returns g != 1) and, when it holds, computes the inverse for free. This single fact is what lets RSA decrypt.
- Base case: gcd(g, 0) returns (g, 1, 0), meaning g = 1*g + 0*0.
- Recursive step: call extended Euclid on (b, a mod b) to get (g, x', y').
- Combine on the way up: return (g, y', x' - (a div b) * y') as the coefficients for (a, b).
- If g = 1 and m was the second input, the first returned coefficient is a's inverse mod m.
Modular exponentiation by repeated squaring
Now the second workhorse: compute a^e mod m where e can be hundreds of bits. The naive loop multiplies a into a running product e times — but e might be 2^1000, so that loop would never finish in the lifetime of the universe; it is exponential in the size of e. Fast modular exponentiation, also called repeated squaring or square-and-multiply, does it in O(log e) multiplications. The idea is to build powers by doubling instead of by adding: a^1, a^2, a^4, a^8, ... each obtained by squaring the previous one. Since any exponent e is a sum of powers of two (its binary digits), a^e is the product of exactly those squared powers whose bit is set.
power(a, e, m): # compute a^e mod m
result = 1
a = a mod m
while e > 0:
if e is odd: # this binary digit of e is 1
result = (result * a) mod m
a = (a * a) mod m # square the running power
e = e div 2 # drop the digit we just used
return resultThe loop runs once per bit of e, so O(log e) iterations, each doing one or two multiplications mod m — that is the whole speedup, exponential value handled in linear-in-the-digits time. The phrase "mod m" inside every line matters as much as the squaring: without it the running power a^(2^k) would grow to billions of digits and each multiplication would itself blow up. Reducing modulo m after every operation keeps every intermediate value below m, so each multiplication stays a fixed-size operation on at most log m bits. Speed comes from two ideas working together: few multiplications (square-and-multiply) and small operands (reduce every time).
Correctness is a clean induction, and it echoes the loop-invariant habit from the foundations rung. Hold this invariant: at the top of each iteration, result * a^e (with the current values of result, a, and e) equals the original a0 raised to the original e0, all mod m. It is true initially (result = 1, a = a0, e = e0). Each iteration preserves it: squaring a and halving e leaves a^e unchanged when e is even, and when e is odd, multiplying result by a absorbs exactly the leftover factor. When e reaches 0, a^e = 1, so result alone equals a0^e0 mod m. The same square-by-doubling pattern, by the way, computes high powers in any setting where multiplication is associative — matrices, polynomials — not just integers mod m.
Where it all leads: RSA and what comes next
Put the pieces together and you can read the algorithmic core of RSA. A public key encrypts a message x by computing c = x^e mod m with fast modular exponentiation; the matching private key decrypts by c^d mod m, where the exponent d is the modular inverse of e (modulo a quantity derived from m's prime factors), found by extended Euclid. Both directions are just repeated squaring; key generation is just GCD and inverse. The security rests not on any of these being slow, but on a different gap: encrypting is easy, while recovering the secret exponent without the factorization of m appears hard. Note the careful wording — "appears hard" reflects that no efficient factoring algorithm is known, which is not the same as a proof that none exists.
The final guide of this rung picks up two threads that start here. First, multiplication of huge integers and polynomials, where the FFT beats the schoolbook O(n^2) — the same divide-and-conquer reflex you met with Karatsuba, pushed to O(n log n). Second, we have been raising things to exponents mod m without asking whether m is prime; the Miller-Rabin test uses modular exponentiation itself as a probe to decide primality quickly, and it is a Monte Carlo algorithm — it can be wrong with controllable probability, a trade we will weigh honestly. Both lean directly on the repeated-squaring engine you just built.