# 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. Sep 30, 2012 at 14:48
• True, but cryptographic techniques involve primes smaller than a number n, where n would be 2^128 Sep 30, 2012 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, 2012 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. Sep 30, 2012 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 Sep 30, 2012 at 15:44

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? Sep 30, 2012 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. Sep 30, 2012 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 ? Sep 30, 2012 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. Sep 30, 2012 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 Sep 30, 2012 at 21:23