RSA Laboratories

3.1.6 Could users of the RSA system run out of distinct primes?

As Euclid proved over two thousand years ago, there are infinitely many prime numbers. Because the RSA algorithm is generally implemented with a fixed key length, however, the number of primes available to a user of the algorithm is effectively finite. Although finite, this number is nonetheless very large. The Prime Number Theorem states that the number of primes less than or equal to n is asymptotic to n/lnn. Hence, the number of prime numbers of length 512 bits or less is roughly 10150. This is greater than the number of atoms in the known universe.

Top of the page