Last Updated: July 15, 2025
Fundamentals
| Concept | Definition | Example |
|---|---|---|
| Prime | Integer > 1 divisible only by 1 and itself | 2, 3, 5, 7, 11, 13, 17, 19, 23 |
| GCD(a,b) | Greatest common divisor | GCD(48, 18) = 6 |
| LCM(a,b) | Least common multiple | LCM(12, 18) = 36 |
| Coprime | GCD(a,b) = 1 | 8 and 15 are coprime |
| φ(n) | Euler's totient — numbers ≤ n coprime to n | φ(10) = 4 ({1,3,7,9}) |
Modular Arithmetic
| Property | Formula |
|---|---|
| Addition | (a + b) mod m = ((a mod m) + (b mod m)) mod m |
| Multiplication | (a × b) mod m = ((a mod m) × (b mod m)) mod m |
| Modular Inverse | a⁻¹ mod m exists iff GCD(a,m) = 1 |
| Fermat's Little | If p prime, a⊥p: a^(p−1) ≡ 1 (mod p) |
| Euler's Theorem | If GCD(a,n)=1: a^φ(n) ≡ 1 (mod n) |
RSA Key Generation
1. Pick primes p, qLarge random primes (2048-bit total)
2. Compute n = p × qModulus — public and private key share n
3. Compute φ(n) = (p−1)(q−1)Euler's totient of n
4. Choose ePublic exponent — 1 < e < φ(n), GCD(e, φ(n)) = 1 (commonly 65537)
5. Compute d = e⁻¹ mod φ(n)Private exponent — extended Euclidean algorithm
Primality Testing
| Test | Type | Speed |
|---|---|---|
| Trial Division | Deterministic — divide by all primes ≤ √n | O(√n) — slow for large n |
| Fermat Test | Probabilistic — check a^(n−1) ≡ 1 mod n | Fast — Carmichael numbers false |
| Miller-Rabin | Probabilistic — k rounds, error ≤ 4⁻ᵏ | Industry standard — k=40 for crypto |
| AKS | Deterministic — polynomial time | Theoretical — too slow in practice |
Pro Tip: Public-key cryptography rests on the hardness of factoring large primes. RSA-2048 would take a classical computer billions of years to break — but Shor's algorithm on a quantum computer changes everything.