Prime Number Magnitudes

If you have an important point to make, don't try to be subtle or clever. Use a pile driver. Hit the point once. Then come back and hit it again. Then hit it a third time - a tremendous whack.

— Winston Churchill

Figure 1: Prime Garden (renoir_girl).

Figure 1: Prime Garden.

I am responsible for some of the authentication features in our products and these features use prime numbers. People often have basic questions on prime numbers, such as:

  • What happens if I choose the same prime number as someone else?
  • Are there enough prime numbers?

I normally give some nebulous answer like "there are more 512-bit prime numbers than there are atoms in the Universe". Recently, I saw a great response on Quora that quoted  Bruce Schneier's Applied Cryptography book on prime numbers. Here are the quotes:

If everyone needs a different prime number, won’t we run out? No. In fact, there are approximately 10^151 primes 512 bits in length or less. For numbers near n, the probability that a random number is prime is approximately one in ln n. So the total number of primes less than n is n /(ln n). There are only 10^77 atoms in the universe. If every atom in the universe needed a billion new primes every microsecond from the beginning of time until now, you would only need 10^109 primes; there would still be approximately 10^151 512-bit primes left.

What if two people accidentally pick the same prime number? It won’t happen. With over 10^151 prime numbers to choose from, the odds of that happening are significantly less than the odds of your computer spontaneously combusting at the exact moment you win the lottery.

If someone creates a database of all primes, won’t he be able to use that database to break public-key algorithms? Yes, but he can’t do it. If you could store one gigabyte of information on a drive weighing one gram, then a list of just the 512-bit primes would weigh so much that it would exceed the Chandrasekhar limit and collapse into a black you couldn't retrieve the data anyway

Schneier's responses are fantastic and I thought I would explore the numbers behind them just a bit more. I plugged some of these number into a Mathcad worksheet and also provided some links to backup material.


number of primes number of atoms mass of the universe
This entry was posted in General Mathematics, software. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *