20050426, 23:11  #1 
2×5×661 Posts 
Prime numbers
Is it possible to get all known prime numbers? (We want to brute force 1024 bits RSA key)

20050427, 00:01  #2  
"William"
May 2003
New Haven
2368_{10} Posts 
Quote:
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 

20081103, 19:12  #3  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
5×7×313 Posts 
Quote:
Think about it before I reveal the answer. Paul 

20081104, 14:56  #4  
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Quote:
Alex 

20081107, 15:25  #5  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2·3^{2}·349 Posts 
Quote:
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_{512} 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^{512}. So we store the log_{512}(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]. 

20081107, 23:43  #6 
Aug 2006
3×1,993 Posts 

20081108, 10:11  #7  
"Nathan"
Jul 2008
Maryland, USA
45B_{16} Posts 
Quote:
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". 

20081108, 18:05  #8  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
5·7·313 Posts 
Quote:
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 

20081109, 07:45  #9 
"Lucan"
Dec 2006
England
2×3×13×83 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
What can you do with 2 prime numbers?  VicDiesel  Programming  12  20170420 21:16 
Right Perfect Prime Numbers  Housemouse  Math  34  20160407 16:29 
Prime Numbers Or Not  Arxenar  Miscellaneous Math  38  20130628 23:26 
All odd numbers are prime  Citrix  Lounge  5  20100405 21:34 
Old Gem Interview about prime numbers  diep  Lounge  3  20090805 21:01 