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?
Prime numbers and their products
-
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
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.
-
0and 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 – 2012-09-30