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^{613}$ primes with exactly 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
• There are about $\frac{2^{1023}}{\ln 2^{1024}} \approx 10^{305}$ primes of 1024 bits, so the chance of two people picking the same prime is essentially zero
• Careful with the 2048-bit figure: $2^{2048} \approx 10^{616}$ counts all numbers below it. Only about one in $\ln 2^{2048} \approx 1420$ of the 2048-bit numbers is prime, which leaves about $10^{613}$

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.