How many prime numbers exist for a given bit length, and why is finding large primes feasible for cryptography?

There are astronomically many primes — about $10^{616}$ primes with 2048 bits, vastly more than atoms in the universe ($10^{80}$). The Gauss pi function estimates: $\pi(x) \approx \frac{x}{\ln(x)}$.

* Gauss's π(x) tracks x/ln(x) closely: primes thin out only slowly, so even among enormous numbers they stay plentiful enough to pick at random. *

Gauss's prime counting function: $$\pi(x) \approx \frac{x}{\ln(x)}$$

This gives the number of primes from 1 to $x$.

The proportion of primes among n-digit odd numbers: $$APZ(n) \approx \frac{2}{\ln(10^n)} = \frac{2}{n \cdot \ln(10)} \approx \frac{1}{1.15 \cdot n}$$

Example for RSA-2048 (needing 1024-bit primes = ~308-digit numbers):

• About every 355th odd 308-digit number is prime
• That's a probability of ~0.28% per random odd number tested
• With $10^{616}$ primes available, the chance of two people picking the same prime is essentially zero

For 150-digit primes (RSA older standard):

• Every ~170th odd number is prime
• Proportion: 0.58%

Tip: This abundance of primes is what makes RSA key generation practical — just pick random odd numbers and test them. You'll find a prime quickly.

Go deeper:

• Prime-counting function (Wikipedia) — π(x), its x/ln x estimate and the prime number theorem.