[Intermediate] — Divisibility, primes and clock arithmetic. Pure mathematics until 1977, then the basis of every secure connection you make.

Divisibility and GCD

means divides exactly.

The greatest common divisor is the largest number dividing both.

Euclid’s algorithm computes it, and it’s the oldest algorithm still in use — about 2,300 years old:

gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6

It runs in — the worst case is consecutive Fibonacci numbers, which is a nice connection to recurrences. Extraordinarily fast, and that efficiency is what makes RSA key generation practical.

Extended Euclid additionally finds with

This is what computes modular inverses, so it’s load-bearing for RSA. Not a curiosity.

Coprime means — no common factor.

Primes

A prime has exactly two divisors: 1 and itself. (1 is not prime, by convention, and the convention exists to make the next theorem true.)

The Fundamental Theorem of Arithmetic: every integer > 1 has a unique prime factorisation.

Euclid: there are infinitely many primes. Assume finitely many, multiply them all and add 1 — the result is divisible by none of them. → Proof by contradiction

The Prime Number Theorem: primes near have density about .

That density is why RSA works. Around , roughly 1 in 710 odd numbers is prime — so generating a random 1024-bit prime takes a few hundred tries, not an astronomical search. Public-key cryptography depends on primes being common enough to find and factoring being hard, and both are facts about how primes are distributed.

Testing primality — and this is the important asymmetry:

Miller–Rabin is a probabilistic test: fast, and wrong with probability for rounds. With 40 rounds the error probability is below the chance of a hardware fault, so it’s what everything actually uses.

AKS (2002) is deterministic polynomial-time — a major theoretical result, too slow in practice.

Testing whether a number is prime is easy. Finding its factors is hard. That gap — polynomial versus (believed) super-polynomial — is the entire foundation of RSA. Note that it’s a believed hardness, not a proven one: nobody has proved factoring is hard, and Shor’s algorithm factors in polynomial time on a quantum computer. → Beyond P vs NP

Modular arithmetic

“Clock arithmetic.” means — they have the same remainder.

It’s an equivalence relation, partitioning into residue classes, and that’s what means.

Arithmetic is well-defined on classes:

Practically: reduce as you go. Computing by computing first will overflow anything. Reducing every step keeps numbers small, and it’s why modular exponentiation is feasible.

Modular exponentiation — square-and-multiply:

result = 1
while exp > 0:
    if exp is odd:  result = result * base % mod
    base = base * base % mod
    exp = exp / 2

multiplications instead of exp. in ten steps. This is the workhorse of public-key crypto, and the reason RSA is usable at all.

Modular inverse

is the value with .

It exists if and only if . Found by extended Euclid.

There’s no division in modular arithmetic — you multiply by the inverse instead. And when is prime, every nonzero element has an inverse, which makes a field. That’s why cryptography and error-correcting codes work over prime moduli.

The two theorems

Fermat’s Little Theorem — for prime and :

The basis of primality testing: if , then is definitely composite. (The converse fails — Carmichael numbers pass for every , which is why Miller–Rabin refines the test.)

Euler’s theorem generalises it:

where counts integers below coprime to it. For with prime, .

That formula is the key to RSA, quite literally.

The Chinese Remainder Theorem — a system of congruences with coprime moduli has a unique solution mod their product. Used to speed up RSA decryption by about 4×, and in secret sharing.

RSA, in full

The payoff, and it’s short enough to state completely:

Key generation

  1. Pick large primes . Let
  2. Compute
  3. Choose coprime to (usually 65537)
  4. Compute — extended Euclid
  5. Public key . Private key . Discard and

Encrypt: Decrypt:

Why it works: by Euler’s theorem.

Why it’s secure: recovering requires , which requires and , which requires factoring . Everyone has ; nobody can factor it at 2048 bits.

Every idea in this note appears in those eight lines — primes, GCD, modular inverse, modular exponentiation, Euler’s theorem. It’s an unusually direct route from elementary number theory to infrastructure that carries the world’s money.

The historical point is worth keeping. G. H. Hardy wrote in 1940 that number theory had no practical application and was proud of it. Thirty-seven years later it became the basis of electronic commerce. “No applications” is a statement about the present, not the subject.

→ Asymmetric Encryption for the practical side — padding (textbook RSA is insecure without OAEP), key sizes, and why elliptic curves are now preferred.

Where else it’s used

Hashing. — and choosing prime matters, because a composite modulus lets patterns in the keys collapse onto few buckets. → Hash Maps

Checksums. ISBN, IBAN, credit card numbers (Luhn), and CRC are all modular arithmetic. A check digit catches single-digit and transposition errors by construction.

Random number generators. LCGs are , and the choice of constants determines the period. → Probability

Error-correcting codes. Reed–Solomon operates over finite fields — Galois fields being modular arithmetic generalised. Used in QR codes, CDs, RAID 6, and deep-space communication.

Circular buffers. index = (index + 1) % size is modular arithmetic and is how ring buffers work.

Diffie–Hellman key exchange — the discrete logarithm problem: given , find . Easy to compute forwards, believed hard backwards — the same one-way asymmetry as factoring, different problem. → Asymmetric Encryption

Practical notes

Negative modulo differs by language. -7 % 3 is 2 in Python and -1 in C, Java and Rust. A real cross-language bug. For a non-negative result: ((a % n) + n) % n.

Overflow before reduction. (a * b) % n overflows if exceeds your integer width even when the result fits. Use a wider type, or __int128, or a bignum.

Use a library for cryptography. Everything here is implementable in an afternoon and that implementation will be broken — timing side channels, weak randomness, missing padding. Implement it to understand it; use libsodium or your platform’s library in production. → Cryptographic Best Practices

Randomness must be cryptographic. rand() seeded from the clock has produced real key compromises. Use /dev/urandom or the OS CSPRNG.

Constant-time comparison for secrets. A comparison that returns early on the first differing byte leaks information through timing.


↑ Back to Discrete Mathematics