Prime numbers

Is it possible to get all known prime numbers? (We want to brute force 1024 bits RSA key)

[wblipp]

Originally Posted by Unregistered

Is it possible to get all known prime numbers? (We want to brute force 1024 bits RSA key)

No.

The number of prime numbers less than "x" is approximately x/ln(x). You might find it interesting to see how much storage space would be required for the primes up to 512 bits - or just the 511 and 512 bit ones.

It will be a very large number. More than can be stored in the universe if you turn all the mass in then universe into extremely efficient storage units.

William

[xilman]

Originally Posted by wblipp

No.

The number of prime numbers less than "x" is approximately x/ln(x). You might find it interesting to see how much storage space would be required for the primes up to 512 bits - or just the 511 and 512 bit ones.

It will be a very large number. More than can be stored in the universe if you turn all the mass in then universe into extremely efficient storage units.

William

In principle it could be stored in a single hydrogen atom.

Think about it before I reveal the answer.


Paul

[akruppa]

Originally Posted by xilman

In principle it could be stored in a single hydrogen atom.

Think about it before I reveal the answer.

Paul

There are infinitely many excitation states of the electron, right? However all but the couple of lowest ones are so close in energy that they will be impossible to distinguish.

Alex

[retina]

Originally Posted by xilman

In principle it could be stored in a single hydrogen atom.

Think about it before I reveal the answer.

Naively we might try to encode all the possible values as a bitmap. Then consider the bitmap as a single large number with 2⁵¹² bits. Then attempt to encode the number in some fashion into the hydrogen atom. But I feel that this approach severely stretches the bounds of credibility and practicality.

Perhaps a better idea is to take into account the fact that no other restrictions have been given with regard to the encoding algorithm. So a better algorithm would seem to be to encode the log₅₁₂ of the required bit count of largest prime to generate. The the generation algorithm would simply return all the primes less then or equal to this value. This means that the required largest prime that we need to generate has a bit count of 512, meaning we need to generate all primes up to 2⁵¹². So we store the log₅₁₂(512), or simply 1. Where 1 means to generate all the primes up to 2^512[sup]1[/sup]. If we were to store 2 in the hydrogen atom then instead we would generate primes up to 2^512[sup]2[/sup].

[CRGreathouse]

Originally Posted by xilman

In principle it could be stored in a single hydrogen atom.

Think about it before I reveal the answer.

It doesn't take any storage space at all, you can just generate them on command. It's like the storage space for the first billion digits of pi.

[NBtarheel_33]

Originally Posted by Unregistered

Is it possible to get all known prime numbers? (We want to brute force 1024 bits RSA key)

Think about it - obviously, the key is designed to be used for secure encryption, hence the designers and users want something that is going to be nigh impossible to break. If what you are thinking of doing were possible, believe me, RSA would be using much, much, much larger keys that would ensure that your brute force attack would take a very, very, very, long time. This is, in fact, why RSA has increased its key size over the years, as advances in computing power have made such brute-force attacks feasible for smaller keylengths.

The only thing that saves our butts with regard to encryption (at least as it stands today) is the fact that integer factorization is essentially impossible for arbitrary integers of any decent size, unless they are of a special form (e.g. Mersenne numbers). Integer factorization problems very, very quickly run into the realm of "oops, the universe is not big enough to hold this calculation".

[xilman]

Originally Posted by akruppa

There are infinitely many excitation states of the electron, right? However all but the couple of lowest ones are so close in energy that they will be impossible to distinguish.

Alex

Give that man a cigar.

The situation becomes slightly more tractable if you put the atom in a magnetic field. The states with the same n but differing l are no longer degenerate.

This storage mechanism is still hopelessly impractical for anything other than a few bits with current technology. Even then, spontaneous emission requires that the memory be refreshed every now and again.


Paul

[davieddy]

Originally Posted by xilman

This storage mechanism is still hopelessly impractical for anything other than a few bits with current technology. Even then, spontaneous emission requires that the memory be refreshed every now and again.


Paul

Does this invoke the "quantum Zeno effect"?