1
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Sep 30, 2012 at 14:48
  • $\begingroup$ True, but cryptographic techniques involve primes smaller than a number n, where n would be 2^128 $\endgroup$ Sep 30, 2012 at 14:51
  • 1
    $\begingroup$ The table might be small enough to fit in memory, but computing the values of the table would probably take too long... $\endgroup$
    – only
    Sep 30, 2012 at 15:01
  • 3
    $\begingroup$ 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. $\endgroup$
    – celtschk
    Sep 30, 2012 at 15:11
  • $\begingroup$ 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 $\endgroup$ Sep 30, 2012 at 15:44

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ one more question, is there any way to estimate the range of primes, that can be the solution? $\endgroup$ Sep 30, 2012 at 19:03
  • $\begingroup$ @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. $\endgroup$
    – mikeazo
    Sep 30, 2012 at 19:11
  • $\begingroup$ ,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 ? $\endgroup$ Sep 30, 2012 at 20:11
  • $\begingroup$ @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. $\endgroup$
    – mikeazo
    Sep 30, 2012 at 20:26
  • $\begingroup$ 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 $\endgroup$ Sep 30, 2012 at 21:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .