Concept
Integers greater than 1 divisible only by 1 and themselves — the multiplicative atoms of whole numbers. Euclid proved there are infinitely many; primes also support several, but not all, modern cryptographic systems.
Understand it in one breath
Numbers greater than one divisible only by 1 and themselves — 2, 3, 5, 7, 11, 13, … The multiplicative atoms of the integers. RSA relies on the apparent classical difficulty of factoring large composites, while internet security combines many cryptographic methods, protocols, and implementations.
At a glance
The first 25 prime numbers |
|---|
2, 3, 5, 7, 11 |
13, 17, 19, 23, 29 |
31, 37, 41, 43, 47 |
53, 59, 61, 67, 71 |
73, 79, 83, 89, 97 |
The atoms of the integers, easily found with the Sieve of Eratosthenes.
Key formula
Worked examples
- 1
Q.Is 6 prime?
- 2
Q.Is 13 prime?
Key moments
Euclid proves there are infinitely many primes
Book IX of the Elements gives an elegant contradiction proof that primes never run out — one of the earliest landmarks of pure mathematics.
The sieve of Eratosthenes
A procedure traditionally attributed to Eratosthenes crosses out successive multiples to leave primes. Later evidence preserves the attribution, not an exact ancient implementation identical to modern code.
The Riemann hypothesis appears
Riemann connected prime distribution to zeros of the zeta function, opening a problem that remains one of the Millennium Prize Problems.
RSA — primes secure digital communication
Rivest, Shamir, and Adleman created public-key cryptography from the asymmetry between multiplying large primes and factoring their product.
Modern applications
RSA and several other constructions use arithmetic built from large primes or finite fields. Internet security also depends on elliptic curves, symmetric ciphers, hashes, protocols, implementations, and key management; primes are important, not the whole system.
Beyond MathVoyage
Loading…