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?

  • $\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$ – Raskolnikov Sep 30 '12 at 14:48
  • $\begingroup$ True, but cryptographic techniques involve primes smaller than a number n, where n would be 2^128 $\endgroup$ – Bartlomiej Lewandowski Sep 30 '12 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 '12 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 '12 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$ – Bartlomiej Lewandowski Sep 30 '12 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.

  • $\begingroup$ one more question, is there any way to estimate the range of primes, that can be the solution? $\endgroup$ – Bartlomiej Lewandowski Sep 30 '12 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 '12 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$ – Bartlomiej Lewandowski Sep 30 '12 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 '12 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$ – Bartlomiej Lewandowski Sep 30 '12 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.