Applications

Overview

Number Theory in Practice

For centuries, number theory was considered "pure" math with no practical applications. That changed dramatically with the advent of computers and cryptography. Today, number theory secures the internet, protects financial transactions, and underlies blockchain technology.

Definition

RSA Cryptosystem (Overview)

RSA is a public-key cryptosystem based on the difficulty of factoring large numbers.

Key Generation: 1. Choose two large primes p and q. Compute n = p × q. 2. Compute φ(n) = (p-1)(q-1) (Euler's totient). 3. Choose e with 1 < e < φ(n) and gcd(e, φ(n)) = 1. 4. Compute d = e⁻¹ mod φ(n) (using extended Euclidean algorithm). 5. Public key: (n, e). Private key: (n, d).

Encrypt: C = Mᵉ mod n. Decrypt: M = Cᵈ mod n.

Example

Toy RSA Example

Choose p = 5, q = 11. n = 55, φ(n) = 4 × 10 = 40. Choose e = 3 (gcd(3, 40) = 1). Find d: 3d ≡ 1 (mod 40). d = 27 (since 3 × 27 = 81 = 2 × 40 + 1).

Public key: (55, 3). Private key: (55, 27).

Encrypt M = 2: C = 2³ mod 55 = 8. Decrypt C = 8: M = 8²⁷ mod 55 = 2. ✓

Definition

Euler's Totient Function

Euler's totient function φ(n) counts the number of integers from 1 to n that are coprime to n.

For prime p: φ(p) = p - 1. For prime power: φ(pᵏ) = pᵏ - pᵏ⁻¹ = pᵏ(1 - 1/p). For coprime a, b: φ(a × b) = φ(a) × φ(b).

Examples: φ(7) = 6, φ(10) = 4 (coprime to 10: 1, 3, 7, 9), φ(12) = 4.

Theorem

Euler's Theorem

If gcd(a, n) = 1, then aᵠ⁽ⁿ⁾ ≡ 1 (mod n).

This generalizes Fermat's Little Theorem (which is the special case where n is prime).

Example: a = 3, n = 10, φ(10) = 4. 3⁴ = 81 ≡ 1 (mod 10). ✓

Note

Other Applications

Number theory also powers: • Hash functions: mapping data to fixed-size values using modular arithmetic. • Error-detecting codes: ISBN, credit card check digits use mod operations. • Random number generation: linear congruential generators use aₙ₊₁ = (a × aₙ + c) mod m. • Cryptographic protocols: Diffie-Hellman key exchange, digital signatures, elliptic curve cryptography.