Prime Numbers

The Most Studied Objects in Mathematics

Prime numbers occupy a singular position in mathematics: they are at once the simplest objects to define and among the most difficult to understand deeply. A prime is a positive integer greater than 1 with no positive divisors other than 1 and itself. From this spare definition flows an extraordinary body of theory touching analysis, algebra, geometry, computation, and cryptography.

The centrality of primes rests on the Fundamental Theorem of Arithmetic, first articulated by Euclid (c. 300 BCE) and rigorously proved by Gauss in Disquisitiones Arithmeticae (1801): every integer greater than 1 factors uniquely into a product of primes. This makes primes the multiplicative atoms of the integers, analogous to chemical elements or basis vectors.

Historical Development

The study of primes is among the oldest branches of mathematics. Key milestones include:

• Euclid's Elements, Book IX, Proposition 20 (c. 300 BCE): The proof that there are infinitely many primes. The argument by contradiction, constructing p₁p₂...p_n + 1, is a model of mathematical elegance and remains the standard introduction to proof technique.
• Eratosthenes' Sieve (c. 240 BCE): The first systematic algorithm for generating primes. Its computational complexity of O(n log log n) was not bettered for sieving algorithms until the 20th century.
• Euler's product formula (1737): Leonhard Euler established the identity ζ(s) = Π (1 - p^-s)^-1, connecting the zeta function to an infinite product over primes. This was the first deep link between analysis and number theory, foreshadowing the analytic methods that dominate modern prime number theory.
• Gauss and Legendre's conjecture (c. 1800): Both independently conjectured that π(x) ~ x/ln(x), based on numerical evidence from tables of primes that Gauss had computed as a teenager.
• Riemann's 1859 paper: In eight pages, Riemann transformed number theory by connecting the distribution of primes to the zeros of the analytically continued zeta function ζ(s) in the complex plane. He stated (but did not prove) what is now the Riemann Hypothesis: all non-trivial zeros have real part 1/2.
• Prime Number Theorem (1896): Independently proved by Hadamard and de la Vallée-Poussin, confirming the Gauss-Legendre conjecture. The proof required showing that ζ(s) has no zeros on the line Re(s) = 1.

Modern Primality Testing

Determining whether a given number is prime is a question with both theoretical and practical significance. The major algorithms include:

• Trial division: Test all divisors up to √n. Simple but O(√n), impractical for large n.
• Miller-Rabin (1976/1980): A probabilistic test. Running k iterations gives a false positive probability of at most 4^-k. Fast (polynomial time), widely used in practice for cryptographic key generation.
• AKS primality test (2002): Agrawal, Kayal, and Saxena proved that primality can be decided in deterministic polynomial time, settling a long-open question. The original algorithm ran in Õ(n¹²) time (later improved to Õ(n⁶)), making it primarily of theoretical importance. In practice, Miller-Rabin with sufficient iterations remains faster.
• Elliptic Curve Primality Proving (ECPP): A practical algorithm for generating primality certificates, general-purpose certificates that can be independently verified. Used for numbers where a verified proof (not just high probability) is required.

Cryptographic Applications

The computational asymmetry between multiplication and factoring underpins modern public-key cryptography. RSA (Rivest-Shamir-Adleman, 1977) selects two large primes p and q (typically 1024 bits each for a 2048-bit key), computes n = pq and the totient φ(n) = (p-1)(q-1), and derives public and private key pairs. The security assumption is that factoring n into p and q is computationally infeasible. The General Number Field Sieve, the fastest known classical factoring algorithm, runs in time exp(O(n^1/3(log n)^2/3)), which is sub-exponential but super-polynomial.

Shor's algorithm (1994) threatens this model: a sufficiently powerful quantum computer could factor n in polynomial time, rendering RSA insecure. This has motivated the NIST Post-Quantum Cryptography Standardization project, with lattice-based and code-based systems being developed as replacements. As of 2024, no quantum computer has factored a cryptographically relevant number, but the transition to post-quantum standards is underway.

The Largest Known Primes

The search for large primes has a long history, from Mersenne's 17th-century investigations to modern distributed computing. Mersenne primes, of the form M_p = 2^p - 1, dominate the record books because the Lucas-Lehmer test provides an efficient primality test specific to this form. As of October 2024, 52 Mersenne primes are known. The largest, 2^136,279,841 - 1, was discovered by Luke Durant using GPU computing through the GIMPS project. It has 41,024,320 decimal digits.

Major Open Problems

• Riemann Hypothesis: All non-trivial zeros of ζ(s) have Re(s) = 1/2. Verified for over 10¹³ zeros. A Millennium Prize Problem ($1M reward). If true, it implies the strongest possible error term in the Prime Number Theorem: |π(x) - Li(x)| = O(√x log x).
• Twin Prime Conjecture: There are infinitely many pairs (p, p+2) where both are prime. Yitang Zhang's 2013 breakthrough showed that there are infinitely many prime pairs with gap at most 70 million. The Polymath project subsequently reduced this bound to 246.
• Goldbach's Conjecture (1742): Every even integer > 2 is the sum of two primes. Verified up to 4 × 10¹⁸. Helfgott (2013) proved the ternary (weak) version: every odd integer > 5 is the sum of three primes.
• Infinitude of Mersenne primes: Unknown. Heuristic arguments (the Wagstaff conjecture) predict infinitely many, growing roughly as e^γ/log 2 · log log x Mersenne primes below 2^x, but no proof exists.