Pure Math to Security
Number theory was long prized as the purest mathematics, studied for its beauty. Today, those same abstract tools secure nearly every online transaction.
Error detection and correction. Check digits use modular arithmetic to catch mistakes. An ISBN's last digit makes a weighted sum , so a wrong digit breaks the congruence. Error-correcting codes extend this to repair corrupted data.
Hashing. A hash function maps keys to a fixed range, typically via reduction modulo a prime. This spreads values evenly for near-instant hash table lookups.
Public-Key Cryptography
RSA public-key cryptography rests entirely on number theory, relying on two large primes whose product is public but whose factors are secret.
| Concept | Role in RSA |
|---|---|
| Modular exponentiation | Fast to compute for encryption/decryption |
| Factoring difficulty | Security rests on the fact that multiplying primes is easy, but factoring their product is hard |
| Euler's theorems | Guarantee that decryption correctly undoes encryption |
Common pitfall: Thinking security comes from a secret algorithm. RSA's method is completely public; the secret is the prime factors, not the procedure.