Number Theory and Cryptography
Number theory studies properties of integers. Once considered purely abstract, it now underpins modern cryptography, hash functions, and error detection — making it vital for computer science.
Divisibility
An integer a divides b (a | b) if b = ak for some integer k. Properties: if a | b and a | c, then a | (b ± c) and a | bc. The Division Algorithm: for integers a and d > 0, there exist unique q and r such that a = dq + r, 0 ≤ r < d.
GCD and Euclidean Algorithm
The Greatest Common Divisor gcd(a, b) is the largest integer dividing both a and b. The Euclidean Algorithm computes gcd efficiently: gcd(a, b) = gcd(b, a mod b), base case gcd(a, 0) = a. The Extended Euclidean Algorithm finds integers x, y such that ax + by = gcd(a, b).
Prime Numbers
A prime number p > 1 has no divisors other than 1 and p. The Fundamental Theorem of Arithmetic: every integer > 1 has a unique prime factorisation. There are infinitely many primes (Euclid's proof). Primality testing includes trial division, Miller-Rabin, and AKS algorithms.
Modular Arithmetic
Modular arithmetic works with remainders: a ≡ b (mod n) if n | (a − b). Modular operations preserve addition and multiplication. Fermat's Little Theorem: if p is prime and gcd(a, p) = 1, then a^(p−1) ≡ 1 (mod p). Euler's theorem generalises this using Euler's totient function φ(n).
Modular Inverses
The modular inverse of a modulo n exists iff gcd(a, n) = 1. It is found using the Extended Euclidean Algorithm. Modular inverses are essential for division in modular arithmetic and key computation in RSA.
RSA Cryptosystem
RSA is a public-key cryptosystem. Key generation: choose primes p, q; compute n = pq and φ(n) = (p−1)(q−1); choose e with gcd(e, φ(n)) = 1; compute d = e⁻¹ mod φ(n). Public key: (n, e). Private key: d. Encryption: c = m^e mod n. Decryption: m = c^d mod n. Security relies on the difficulty of factoring n.
Hash Functions
Cryptographic hash functions map input to a fixed-size digest. Properties: deterministic, fast, pre-image resistant, collision resistant. Examples: SHA-256, MD5 (broken). Applications include digital signatures, password storage, and data integrity verification.
Summary
Number theory provides the mathematical foundation for modern cryptography. Divisibility, primes, modular arithmetic, and the RSA algorithm are essential knowledge for understanding security in computer systems.