19. Number Theory Basics

Level: Intermediate You'll use this for: the mathematical foundation of every public-key cryptosystem (Ch. 24).

Prime numbers

A prime has exactly two divisors: 1 and itself. Primes are the "atoms" of multiplication — every integer > 1 has a unique prime factorization (the Fundamental Theorem of Arithmetic). Factoring a number back into its primes is believed to be computationally hard for large numbers — this single asymmetry (easy to multiply two primes, hard to factor the product back apart) is the entire basis of RSA (Ch. 24).

GCD and the Euclidean algorithm

The greatest common divisor of two numbers, computed efficiently:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

gcd(48, 18)   # 6

Tracing it by hand — repeatedly replace the larger number with the remainder of dividing it by the smaller, until the remainder hits 0:

gcd(48, 18):
  48 = 2×18 + 12    ->  gcd(48,18) = gcd(18,12)
  18 = 1×12 + 6     ->  gcd(18,12) = gcd(12,6)
  12 = 2×6  + 0     ->  remainder is 0, STOP

The last non-zero remainder is the GCD: 6.

Why this works: any number that divides both 48 and 18 must also divide their difference (and therefore their remainder) — so gcd(48,18) = gcd(18,12) = gcd(12,6) = 6. Each step shrinks the numbers fast (roughly by half every two steps), which is exactly why this runs in O(log(min(a,b))) instead of checking every possible common divisor.

This 2,300-year-old algorithm (Euclid, ~300 BCE) runs in O(log(min(a,b))) time — remarkably fast — and is a core primitive inside RSA key generation and modular inverse computation.

Modular inverse and Fermat's Little Theorem

The modular inverse of a mod n is a number x such that a·x ≡ 1 (mod n) — "division" in modular arithmetic. Fermat's Little Theorem: if p is prime and a is not a multiple of p, then a^(p-1) ≡ 1 (mod p). This theorem is the basis for:

1. Fast primality testing (Fermat/Miller-Rabin primality tests).
2. Computing modular inverses efficiently.
3. Part of the mathematical machinery behind RSA's correctness proof.

# Modular inverse via Python's built-in pow() with a negative exponent (3-arg pow)
a, n = 3, 11
inverse = pow(a, -1, n)
print(inverse)                 # 4, because 3*4 = 12 ≡ 1 (mod 11)
print((a * inverse) % n)       # 1

Finding that inverse by hand — for small numbers, just try multiplying a by each candidate x from 1 upward until you hit ≡ 1 (mod n):

Find x such that 3x ≡ 1 (mod 11):
  3×1 = 3    mod 11 = 3    no
  3×2 = 6    mod 11 = 6    no
  3×3 = 9    mod 11 = 9    no
  3×4 = 12   mod 11 = 1    yes!  -> inverse of 3 mod 11 is 4

This brute-force search works fine for small n, but for cryptographic sizes (hundreds of digits) it's infeasible — real implementations use the extended Euclidean algorithm, which runs the GCD trace above backwards, substituting each remainder equation back into the previous one to express 1 as 3·x + 11·y, and reads x mod 11 off as the inverse — same O(log n) speed as ordinary GCD, just tracked with extra bookkeeping at each step.

Euler's totient function

φ(n) counts how many integers from 1 to n are coprime to n (share no common factor). For a prime p: φ(p) = p - 1. For n = p·q (product of two distinct primes): φ(n) = (p-1)(q-1). This exact formula is the crux of RSA key generation (Ch. 24 walks through the full derivation).

Why (p-1)(q-1)? Out of 1 … pq, the numbers that do share a factor with pq are the multiples of p (there are q of them) and the multiples of q (there are p), and pq itself got counted twice. So φ(pq) = pq - q - p + 1 = (p-1)(q-1). That's inclusion–exclusion, the same "subtract the overlap" move as P(A ∪ B) in Ch. 8.

Reading modular notation

a ≡ b (mod n)      "a is congruent to b modulo n"

Why must gcd(a, n) = 1? If a and n share a factor g > 1, every multiple a·x is also a multiple of g, and so is n. So a·x mod n is always a multiple of g and can never equal 1. That's why e in RSA must be coprime to φ(n).

The extended Euclidean algorithm, by hand

This is the real algorithm that computes RSA's private exponent. We want d = 17⁻¹ (mod 3120), the numbers from Ch. 24's toy RSA.

Forward pass: plain GCD, but keep the quotients.

3120 = 183 · 17 + 9
  17 =   1 ·  9 + 8
   9 =   1 ·  8 + 1      <- remainder 1, so gcd = 1 and an inverse exists

Backward pass: write 1 as a combination of 3120 and 17.

1 = 9 - 1·8                              (from line 3)
  = 9 - 1·(17 - 1·9)    = 2·9 - 17       (substitute line 2 for the 8)
  = 2·(3120 - 183·17) - 17               (substitute line 1 for the 9)
  = 2·3120 - 367·17

Reduce mod 3120 and the 2·3120 term vanishes: -367 · 17 ≡ 1. So d ≡ -367 ≡ 3120 - 367 = 2753 (mod 3120). That's exactly what pow(17, -1, 3120) returns. Bézout's identity is the theorem behind this: for any a, b there are integers x, y with a·x + b·y = gcd(a, b), and the algorithm finds them.

Fermat's Little Theorem, proved

Theorem (Fermat, 1640). If p is prime and p ∤ a, then a^(p-1) ≡ 1 (mod p).

Proof idea. Multiply every non-zero residue 1, 2, …, p-1 by a. Because a has an inverse, no two products can collide (if a·i ≡ a·j, multiply by a⁻¹ and i ≡ j). So the products are the same p-1 numbers, just shuffled:

(a·1)(a·2)…(a·(p-1)) ≡ 1·2·…·(p-1)     (mod p)
a^(p-1) · (p-1)!     ≡ (p-1)!          (mod p)
a^(p-1)              ≡ 1               (cancel (p-1)!, which is invertible mod p)

Example: 3¹⁰ mod 11. Here p = 11, so the theorem says the answer is 1, with no multiplying needed. (Check: 3⁵ = 243 = 22·11 + 1, so 3⁵ ≡ 1 and 3¹⁰ ≡ 1.) ✓

Euler's theorem generalizes it to any modulus, which is what RSA needs:

a^φ(n) ≡ 1 (mod n)          whenever gcd(a, n) = 1

The proof is the same shuffle, done over the φ(n) invertible residues instead of all p - 1. Example: the last two digits of 7²⁰²⁶. We need 7²⁰²⁶ mod 100. φ(100) = 40 and gcd(7, 100) = 1, so 7⁴⁰ ≡ 1. Then 2026 = 50·40 + 26, which gives 7²⁰²⁶ ≡ 7²⁶ (mod 100), and square-and-multiply (Ch. 24) gives 49. Exponents can always be reduced mod φ(n). That one fact is why RSA decryption works (Ch. 24).

Primality testing: how openssl genrsa finds primes

How many candidates? The Prime Number Theorem says primes near N have density about 1 / ln N:

π(N) ≈ N / ln N        (π(N) here = number of primes ≤ N, not 3.14...)

For a 1024-bit prime (half of an RSA-2048 key), ln(2¹⁰²⁴) ≈ 710. One random 1024-bit number in 710 is prime, or one in about 355 if you only try odd numbers. That's a few hundred candidates, each tested in milliseconds.

How to test each candidate? Fermat's theorem gives a test: if a^(n-1) mod n ≠ 1, then n is definitely composite. But some composites pass for every coprime a. These are the Carmichael numbers, and the smallest is 561 = 3·11·17, with 2⁵⁶⁰ ≡ 1 (mod 561) even though 561 isn't prime. Miller–Rabin closes that hole by also checking square roots of 1 along the way. Each random round catches a composite with probability at least 3/4, so k rounds leave an error below 4⁻ᵏ. With 64 rounds that's 2⁻¹²⁸, far less likely than a cosmic-ray bit flip in your RAM.

The Chinese Remainder Theorem (CRT)

Theorem. If n₁, n₂, …, nₖ are pairwise coprime, then the system x ≡ a₁ (mod n₁), …, x ≡ aₖ (mod nₖ) has exactly one solution modulo N = n₁·n₂·…·nₖ.

Knowing a number mod 3, mod 5 and mod 7 pins it down mod 105. The classic puzzle from the 3rd-century Sunzi Suanjing: find x with x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7). Answer: 23. (23 = 7·3 + 2 = 4·5 + 3 = 3·7 + 2 ✓)

Security in the wild: RSA-CRT is 4× faster, and dangerous. Every real RSA implementation signs with CRT. Instead of one exponentiation mod n (2048 bits), it does two mod p and mod q (1024 bits each) and recombines. Exponentiation cost grows roughly with the cube of the bit length, so two half-size exponentiations cost about 2 · (1/2)³ = 1/4 of one full-size one.

The danger is the Bellcore fault attack (Boneh, DeMillo & Lipton, 1997). If a glitch (voltage spike, Rowhammer, cosmic ray) corrupts only the mod-p half, the faulty signature s' is still correct mod q but wrong mod p. Then s'ᵉ - m is divisible by q but not by p, so:

gcd(s'ᵉ - m, n) = q        -> the private key falls out of one bad signature

With the toy key (n = 3233 = 61·53), signing m = 65 with a corrupted mod-61 half gives s' = 2602 instead of 588, and gcd(2602¹⁷ - 65 mod 3233, 3233) = 53. That's why OpenSSL and HSMs verify every signature before releasing it, which costs one cheap public-key operation.

Security in the wild: batch GCD on the internet's keys

If two RSA keys accidentally share a prime, as in n₁ = p·q₁ and n₂ = p·q₂, then gcd(n₁, n₂) = p breaks both keys instantly, with no factoring needed. Toy example: gcd(3233, 4331) = 61. In 2012 Heninger et al. ("Mining Your Ps and Qs") ran a fast batch-GCD across millions of TLS and SSH keys collected from the internet. They factored the keys of about 0.5% of TLS hosts, mostly embedded routers and firewalls that generated keys at first boot, before the kernel had gathered enough entropy (Ch. 23). Euclid's 2,300-year-old algorithm broke real devices in production.

Real-life engineering ties

• Security/Crypto: this entire chapter is direct preparation for understanding why RSA, Diffie-Hellman, and DSA work — not just how to call the library functions (Ch. 24).
• SWE: hash function design borrows number-theoretic properties (good hash functions often use large primes to reduce clustering).
• Network: less direct, but TLS/SSH key exchange (used on every HTTPS connection) is number theory in production.

More real-life examples:

• Generating a GPG/PGP or TLS certificate key pair involves searching for large probable primes using fast primality tests (Miller-Rabin, built on Fermat's Little Theorem) — a process you can watch run (openssl genrsa pausing while it searches) every time a key is generated.
• NIST formally deprecated 1024-bit RSA keys around 2013-2015 specifically because advances in factoring algorithms and computing power eroded their safety margin — a dated, real-world consequence of the factoring-hardness assumption discussed in the common mistake below.
• Blockchain wallet addresses are derived from elliptic-curve public keys (Ch. 24), which rest on the same finite-field number theory as this chapter — losing the private key (a large number) means losing the funds forever, with no "reset password" option.
• Historical cryptanalysis of the Enigma machine at Bletchley Park exploited structural weaknesses (a letter could never encrypt to itself) rather than breaking the underlying math — an early lesson that a cipher's implementation details matter as much as its theoretical hardness.

Common mistake

Believing "prime factorization is hard" is a proven mathematical fact — it is not proven; it's a widely believed, extensively tested computational hardness assumption. This distinction matters: it's why "post-quantum" cryptography exists — Shor's algorithm, running on a sufficiently large quantum computer, would break this assumption efficiently, which is why NIST has standardized quantum-resistant alternatives (ML-KEM, ML-DSA) as of 2024.