How prime numbers and modular arithmetic protect the digital world.
Why Number Theory?
Public-key cryptography relies on trapdoor functions — easy to compute but hard to invert. The difficulty of factoring large numbers into primes and computing discrete logarithms provides these trapdoors. What was once "pure" mathematics is now essential to internet security.
e = 17 (coprime to 3120). d = 2753 (since 17 × 2753 = 46801 ≡ 1 mod 3120)
Encrypt m = 65: c = 65¹⁷ mod 3233 = 2790
Decrypt: 2790²⁷⁵³ mod 3233 = 65 ✓
Security relies on: factoring n = pq is hard when p, q are ~1024 bits each. Euler's theorem guarantees decryption works: m^(ed) ≡ m^(1 + kφ(n)) ≡ m (mod n).
Diffie-Hellman Key Exchange
Public: large prime p, generator g
Alice sends: A = gᵃ mod p (a is secret)
Bob sends: B = gᵇ mod p (b is secret)
Shared secret: s = Bᵃ = Aᵇ = gᵃᵇ mod p
Security relies on the Discrete Logarithm Problem: given g, p, and gᵃ mod p, finding a is computationally difficult. This uses the same modular exponentiation techniques.
Modern Topics
Elliptic Curve Cryptography (ECC): Uses algebraic curves over finite fields — same security with smaller keys
Hash functions: One-way mappings used in digital signatures
Zero-knowledge proofs: Prove knowledge without revealing information
Quantum computers could break RSA and Diffie-Hellman using Shor's algorithm (efficient prime factorization). The cybersecurity community is actively transitioning to quantum-resistant algorithms based on lattices, codes, and hash functions — all rooted in mathematics from linear algebra and number theory.