Testing, counting, encrypting
This guide answers two linked questions: how to decide whether a whole number is prime, and why primes sit at the heart of modern encryption. You will get a repeatable primality test, a way to estimate prime counts below any limit, and a clear picture of why multiplying two secret primes produces a hard-to-break key.
Key quantities
| Quantity | Value | What it tells you |
|---|---|---|
| Primes below 100 | 25 | Small end of the sequence, verifiable by hand |
| Primes below 1 billion | 50,847,534 | Concrete count confirming the x / ln x estimate |
| Trial division bound | √n | Largest candidate divisor you ever need |
| 6k ± 1 wheel reduction | 2 of 6 candidates | Two thirds of the work removed up front |
| RSA-2048 modulus | 2048 bits, ~617 digits | Product of two secret primes |
| Miller-Rabin deterministic range | below 3.3 × 10^24 | Fixed small bases settle primality exactly |
| Largest known Mersenne prime (Oct 2024) | 2^136279841 − 1 | 41,024,320 decimal digits |
| Goldbach verification limit | 4 × 10^18 | Every even number below checked as two primes |
Trial division up to the square root of n gives a definitive yes or no.
Start with the number n itself. If n is less than 2 it is not prime. If n equals 2 or 3 it is prime. If n is divisible by 2 or 3, stop: it is composite.
Otherwise test only candidates of the form 6k − 1 and 6k + 1, up to and including the square root of n. If none of them divides n, the number is prime.
The square-root bound is what makes the method practical. A composite number always has a factor at or below its square root, so anything larger than that cannot reveal a new divisor.
Every figure on this page comes from a stated, checkable result: exact prime counts, the prime number theorem, the square-root bound, and published RSA key sizes. Nothing here is estimated for effect.
Sources
Figures drawn from standard results in number theory and public cryptography references.