mersenneforum.org Prime numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2005-04-26, 23:11 #1 Unregistered   3·5·109 Posts Prime numbers Is it possible to get all known prime numbers? (We want to brute force 1024 bits RSA key)
2005-04-27, 00:01   #2
wblipp

"William"
May 2003
New Haven

23·5·59 Posts

Quote:
 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

2008-11-03, 19:12   #3
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

28×41 Posts

Quote:
 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.

Paul

2008-11-04, 14:56   #4
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts

Quote:
 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

2008-11-07, 15:25   #5
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

2×34×37 Posts

Quote:
 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 2512 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 log512 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 2512. So we store the log512(512), or simply 1. Where 1 means to generate all the primes up to 2512[sup]1[/sup]. If we were to store 2 in the hydrogen atom then instead we would generate primes up to 2512[sup]2[/sup].

2008-11-07, 23:43   #6
CRGreathouse

Aug 2006

3×1,987 Posts

Quote:
 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.

2008-11-08, 10:11   #7
NBtarheel_33

"Nathan"
Jul 2008
Maryland, USA

111510 Posts

Quote:
 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".

2008-11-08, 18:05   #8
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

290016 Posts

Quote:
 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

2008-11-09, 07:45   #9
davieddy

"Lucan"
Dec 2006
England

2×3×13×83 Posts

Quote:
 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"?

 Similar Threads Thread Thread Starter Forum Replies Last Post VicDiesel Programming 12 2017-04-20 21:16 Housemouse Math 34 2016-04-07 16:29 Arxenar Miscellaneous Math 38 2013-06-28 23:26 Citrix Lounge 5 2010-04-05 21:34 diep Lounge 3 2009-08-05 21:01

All times are UTC. The time now is 07:28.

Sun Jan 17 07:28:09 UTC 2021 up 45 days, 3:39, 0 users, load averages: 2.92, 2.14, 1.91