On this page
1. What makes a number prime
A prime is a whole number greater than 1 divisible only by 1 and itself. 2, 3, 5, 7, 11, 13 — and on forever, in a sequence nobody has ever found a simple formula for.
Everything else is composite, and every composite number breaks apart into primes in exactly one way. That is the fundamental theorem of arithmetic, and the uniqueness is the part cryptography cares about.
3233 = 61 × 53 (the only way)
2. There are infinitely many
Euclid proved it around 300 BC, and the argument still fits in a paragraph. Suppose primes ran out, and you had a complete list. Multiply them all together and add 1. The result is divisible by none of them — it always leaves remainder 1. So either it is a new prime, or it has a prime factor missing from your list. Either way the list was incomplete.
Primes thin out as numbers grow, but they never stop. Near a number n, roughly one in every ln(n) numbers is prime — so among 300-digit numbers, about one in 700. Rare, but nowhere near rare enough to run out.
3. Finding 300-digit primes
RSA needs two primes of about 300 digits each. You cannot look those up in a table — there are more of them than atoms in the observable universe. They are generated on demand.
Guess
Pick a random odd number of the right size.
Screen it
Divide by the small primes — 3, 5, 7, 11 and so on. This throws out most candidates almost instantly.
Test it properly
Run the Miller–Rabin test, which builds on Fermat's little theorem. Each round either proves the number composite or raises confidence it is prime.
Miller–Rabin is probabilistic: it can be wrong, but the chance halves with every round. Forty rounds leave a false-positive probability below 1 in 10²⁴ — far less likely than your hardware failing mid-calculation.
Crucially, this proves a number is prime without factoring it. Recognising a prime is easy; taking a composite apart is not.
4. Why factoring is the hard direction
Multiplying two 300-digit primes takes microseconds. Recovering them from the product is the problem the entire security of RSA rests on.
The best known classical algorithm, the general number field sieve, runs in sub-exponential time — fast enough to have broken 512-bit and 768-bit moduli, nowhere near fast enough for 2048-bit ones. Nobody has ever proved factoring is hard. It is an assumption, tested by fifty years of failed attempts.
Shor's algorithm would factor efficiently on a large quantum computer, which is why post-quantum cryptography exists.
5. Where primes show up in real systems
In RSA, two secret primes generate the public modulus. In Diffie–Hellman, a large prime defines the field the key exchange happens in. In elliptic curve cryptography, curves are defined over a prime field, and the number of points on the curve is chosen to have a large prime factor.
Different mathematics, same dependency: a hard problem sitting on top of prime structure.
Factor one yourself
Break n = 3233 back into its primes and recover the message — the same attack, at readable scale.
Try the RSA boss battle →Frequently asked questions
- Why does cryptography use prime numbers?
- Because multiplying primes is easy while factoring the product is extremely hard. That gap between the easy and hard direction is what makes public-key encryption possible.
- How are large primes found?
- By generating random odd numbers of the right size, screening them against small primes, and running probabilistic tests such as Miller-Rabin until the chance of error is negligible.
- How big are the primes used in RSA?
- For a 2048-bit RSA key each prime is about 1024 bits, roughly 300 decimal digits.
- Is factoring proven to be hard?
- No. It is an assumption, not a theorem. It has resisted serious effort for decades, but no proof of hardness exists — and quantum computers would break it entirely.