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?

  • 0
    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.2012-09-30
  • 0
    True, but cryptographic techniques involve primes smaller than a number n, where n would be 2^1282012-09-30
  • 1
    The table might be small enough to fit in memory, but computing the values of the table would probably take too long...2012-09-30
  • 3
    There are more than $2^{120}$ primes below $2^{128}$ (using the formula from [this question](http://math.stackexchange.com/q/102291/34930)). 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.2012-09-30
  • 0
    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 22012-09-30
  • 0
    @coolbartek, for RSA (say) N is at least 1024 bits (now days more like 2048). That means the primes are 512 bits (or 1024 bits). Current [factoring methods](http://en.wikipedia.org/wiki/Integer_factorization) will be much faster (yet still infeasible for secure RSA). I think there are a few factoring related question you might find interesting on [Crypto.SE](http://cryptography.stackexchange.com).2012-09-30

1 Answers 1

1

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.

  • 0
    one more question, is there any way to estimate the range of primes, that can be the solution?2012-09-30
  • 0
    @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.2012-09-30
  • 0
    ,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 ?2012-09-30
  • 0
    @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.2012-09-30
  • 0
    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 answers2012-09-30