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
    @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
    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