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. 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.
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 — 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. 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.
Cryptography lives or dies on prime arithmetic, and the looming threat is quantum: Shor's algorithm (1994) factors integers in polynomial time on a sufficiently large quantum computer, which is why NIST has been standardizing post-quantum replacements — lattice-based, hash-based — since 2016, with enterprises mid-migration. Outside cryptography, primes underwrite hash tables (prime moduli spread collisions), randomized fingerprinting, and probabilistic primality tests for key generation. The Riemann Hypothesis remains the most famous unsolved problem in mathematics; a proof would settle a thousand subordinate conjectures and clarify how secure the cryptographic constructions built on prime arithmetic actually are.