Q: How hard would it be to make a list of products of primes that could beat public key encryption?

The complete question was: I’m assuming almost anyone with sufficient computing power could generate big prime numbers (if these are not already published somewhere). Would making a table of all of the products of these prime numbers be so difficult? Published public keys could then be compared to this list and the prime factors would be known immediately with a simple database look-up. Wouldn’t this make public key cryptography useless?

Mathematician: Let’s say we are working with all prime numbers that are about d digits long or shorter. The largest such number is x=10^d – 1. The number of prime numbers less than this (applying the prime number theorem) is about which is approximately equal to . Making a table of the product of all of these primes would mean storing about squared numbers, which is about

numbers. The average size of one of these numbers is about

.5 x 10^d

Hence, on average one of these products will be larger than

.25 x 10^2d

which takes about

6.64 d

bits to store. The total number of bits needed will be about the number of bits per number times the number of numbers. The number of numbers though is about giving a total number of bits of about

converting this to gigabytes, we have about

gigabytes.

If we set d=100 (corresponding to storing all products of prime numbers with no more than 100 digits each) that requires about

1.12 x 10¹⁸⁹

which is a ridiculously huge number… far, far bigger than the entire size of the internet. For comparison, the Earth only has about 10⁵⁰ atoms.

If we set d=20 (corresponding to storing all products of prime numbers with no more than 20 digits each) that requires about

5.6 x 10²⁹
which is still much bigger than the size of the internet!

Basically, there are far too many large prime numbers to store them all, even if we restrict ourselves only to numbers of 20 digits in length.

Physicist: This isn’t an answer, just a clarification of what the question was about (for those of you who aren’t hip to the Comp Sci scene), followed by something I think is worth knowing.

Public key encryption is based on a “trap door algorithm”. Basically, you use a mathematical process that is easy to do in one direction and nie-impossible to do in the other direction, unless you know the “secret”. RSA encryption uses multiplication as it’s mathematical process. (There’s a bit more to it, and if anyone wants to know more let us know.)

Multiplication is easy: 170,363 x 83,701,993 = ?

Factoring is hard (secret = knowing the factors): ? x ? = 14,259,722,633,459

Cryptographers like prime numbers because by using only two big primes you make sure that your factors are large and hard to find. If you have b factors, then, for a given product N, the average size of each factor is about (smaller and easier to find for larger b).

If you’re ever bored and want to find a big prime you can use Fermat’s Little Theorem: if (for 1 < x < P), then P is almost certainly prime. “mod P” just means “when the numbers involved get bigger than P, just subtract P a few times until you’re below P again”. You can do this with pencil and paper, even for huge numbers.

So for example: P = 7, and x= 5 (pick x at random). 5⁶ mod 7 = (5²)³ mod 7 = (25)³ mod 7 = (21+4)³ mod 7 = (4)³ mod 7 = 64 mod 7 = 63+1 mod 7 = 1. 7 is almost definitely prime!

To be more sure you can check a couple different x’s. False positives are very rare using this test.

Another example: P = 12, x=3. 3¹¹ mod 12 = 3⁸⁺³ mod 12 = ((3²)²)²3³ mod 12 = (9²)²27 mod 12 = (81)²(24+3) mod 12 = (72+9)²3 mod 12 = (9)²3 mod 12 = 81 x 3 mod 12 = (72+9)3 mod 12 = 9 x 3 mod 12 = 27 mod 12 = 3 ≠ 1. 12 is not prime!

Fermat’s Little Theorem is a nearly 100% accurate test, but if you’re some kind of mathematician or something you would want to use the algorithm found in “Primes is in P” (by Agrawal, Kayal, Saxena). This doesn’t have much to do with the original question, but I think it’s worth knowing.