# Prime numbers and their products

I've been reading a bit about prime numbers and their use in cryptography. If i would create a table of primes and their products, would there be any way to point out the area where a given number x would be? (X will only be a product of two primes) For example, number 15 is a product of prime number at position 3 and 4.(1,2,3,5) Would a table of those numbers be small enough to fit in a computer memory?

• There are an infinite amount of prime numbers, however large your computer memory, I'll always be able to find prime numbers that are not in it. – Raskolnikov Sep 30 '12 at 14:48
• True, but cryptographic techniques involve primes smaller than a number n, where n would be 2^128 – Bartlomiej Lewandowski Sep 30 '12 at 14:51
• The table might be small enough to fit in memory, but computing the values of the table would probably take too long... – only Sep 30 '12 at 15:01
• There are more than $2^{120}$ primes below $2^{128}$ (using the formula from this question). Given that to store one number, you need $128$ bits = $16$ bytes, you'd need more than $2^{124}$ bytes to store all those numbers. With 1 TB = $2^{40}$ bytes, that means you'd need $2^{64}\approx 1.8\cdot 10^{19}$ Terabyte disks to store those numbers. So no, the list definitely would not be small enough to fit in memory. – celtschk Sep 30 '12 at 15:11
• how about finding a range of primes that can be a factor of a number? It would be pointless to go through all of them to find the 2 – Bartlomiej Lewandowski Sep 30 '12 at 15:44

## 1 Answer

So say you are trying to defeat RSA-1024. Each of the 2 primes to generate the RSA keypair is approximately 512 bits.

According to the Prime Number Theorem, there are approximately $\frac{n}{\ln{n}}$ prime numbers less than $n$.

Say we assume that both primes are between 510 bits and 512 bits. There are approximately $2^{503}$ primes less than $2^{512}$. Subtract off all primes that are 509 bits and less (there are approximately $2^{500}$ such primes) and we are left with $2^{503} - 2^{500}\approx 2^{502}$.

Therefore, there are approximately $2^{502}$ primes you would have to store. There are approximately $2^{265}$ atoms in the known universe. So, even if each atom could store one prime number, you wouldn't be able to store all of the primes for the given range.

• one more question, is there any way to estimate the range of primes, that can be the solution? – Bartlomiej Lewandowski Sep 30 '12 at 19:03
• @coolbartek, It depends on the implementation. Some will allow any prime of say 512 bits or less. Others will force the most-significant-bit to be 1, thus forcing it to be only 512 bit numbers. It all depends. – mikeazo Sep 30 '12 at 19:11
• ,What i meant was, for a number x that is a product of two primes, is there a way to estimate that the primes(a,b) are a number that c < a,b < d ? – Bartlomiej Lewandowski Sep 30 '12 at 20:11
• @coolbartek, not that I know of. Might be a good question for here or crypto.SE. My guess is that there isn't because, for example you could have a 1000 bit prime multiplied by a 24 bit prime and still get a 1024 bit prime. – mikeazo Sep 30 '12 at 20:26
• and there is at least one more prime for every other bit since there is at least one prime between n and 2n. Thanks for the answers – Bartlomiej Lewandowski Sep 30 '12 at 21:23