The Fundamental Theorem of Arithmetic

Every integer greater than 1 factors uniquely into a product of primes. This uniqueness is what makes factoring interesting as a hard problem: if factoring were not unique, the structure RSA relies on would collapse. Generating large primes efficiently is

Euler's Phi Function and RSA Key Generation

Euler's totient phi(n) counts the integers in {1, ..., n} that are coprime to n. For a prime p, phi(p) = p-1. For a product of two distinct primes n = pq, phi(n) = (p-1)(q-1). RSA key generation chooses e coprime to phi(n) and computes d such that e*d = 1

The Chinese Remainder Theorem

If n = pq with p and q coprime, then Z_n is isomorphic to Z_p x Z_q: every computation mod n corresponds to a pair of computations mod p and mod q. RSA decryption using CRT computes m^d mod p and m^d mod q separately (with smaller, faster exponentiations)

Quadratic Residues and Point Decompression

An integer a is a quadratic residue mod p if there exists x with x^2 = a mod p. The Legendre symbol (a|p) is 1 if a is a nonzero QR, -1 if not, and 0 if p divides a. The Tonelli-Shanks algorithm computes square roots mod p in polynomial time. Elliptic cur

Miller-Rabin Primality Testing

Miller-Rabin is a probabilistic primality test based on the Fermat test and additional structure of composites. A composite passes any single round with probability at most 1/4. Running 40 independent rounds gives a false-positive probability of at most 2