Primes & Factorization

In Book IX, Proposition 20 of Euclid's Elements (~*300 BCE*) appears one of the oldest and most beautiful proofs in mathematics: there are infinitely many primes. Suppose finitely many; multiply them all; add 1; the result is either a new prime or has a prime factor not in the list — contradiction either way. The argument matters because the primes are the multiplicative atoms of arithmetic — every whole number is built by multiplying them, and Euclid had just shown the supply of atoms never runs out. The reasoning is a proof by contradiction so clean it survives intact in every modern textbook, needing neither symbols nor calculation, only the certainty that a finite list can always be outrun. Republished, translated, and admired for twenty-three centuries, the theorem still stands as the foundation under which all of modern number theory operates.

Primes are the multiplicative atoms of the integers. The Fundamental Theorem of Arithmetic says every integer above one factors uniquely into primes — 60 = 2²·3·5, and there is no other way — making the primes a periodic table for the natural numbers, with deep questions of number theory tending to reduce to questions about them. Uniqueness is what gives the atoms their meaning: change one factor and you change the number, and a single shared prime factor is what makes two numbers divisible by the same thing. The first few primes — 2, 3, 5, 7, 11, 13 — look almost ordinary; the difficulty is that no formula generates them, only the sieve of Eratosthenes and its descendants, crossing out multiples until the survivors remain.

Primes are not distributed in any obvious pattern, yet they are not random. They thin out predictably — the Prime Number Theorem (Hadamard, de la Vallée Poussin, 1896) shows the number of primes below N is asymptotically N / ln N, so primes near a large number N arrive about once every ln N steps — but local fluctuations remain mysterious. The Riemann Hypothesis (Riemann, 1859) claims all non-trivial zeros of the zeta function lie on a single vertical line in the complex plane; if true, it gives the tightest possible error bound on the prime-counting function. RH is a Clay Millennium Prize problem, with a long catalogue of related conjectures around it — twin primes, Goldbach, Polignac.

What makes this more than a connoisseur's pursuit is that the factoring problem — given a large integer, find its prime factors — is widely believed to be computationally hard. Multiplying two primes is trivial; recovering them from the product is not. No polynomial-time classical algorithm is known; the number field sieve runs in sub-exponential time and becomes infeasible on integers of a few thousand bits. RSA encryption and most public-key cryptography rest on this gap between multiplication (easy) and factoring (apparently hard) — a gap entangled with P-vs-NP and with quantum machines.