mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2005-04-26, 23:11   #1
Unregistered
 

1BBB16 Posts
Default Prime numbers

Is it possible to get all known prime numbers? (We want to brute force 1024 bits RSA key)
  Reply With Quote
Old 2005-04-27, 00:01   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×32×5×13 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2008-11-03, 19:12   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

236218 Posts
Default

Quote:
Originally Posted by wblipp View Post
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
xilman is offline   Reply With Quote
Old 2008-11-04, 14:56   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25×7×11 Posts
Default

Quote:
Originally Posted by xilman View Post
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
akruppa is offline   Reply With Quote
Old 2008-11-07, 15:25   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

32×647 Posts
Default

Quote:
Originally Posted by xilman View Post
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].
retina is online now   Reply With Quote
Old 2008-11-07, 23:43   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

17×349 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
CRGreathouse is online now   Reply With Quote
Old 2008-11-08, 10:11   #7
NBtarheel_33
 
NBtarheel_33's Avatar
 
"Nathan"
Jul 2008
Maryland, USA

3×7×53 Posts
Default

Quote:
Originally Posted by Unregistered View Post
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".
NBtarheel_33 is offline   Reply With Quote
Old 2008-11-08, 18:05   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

7·1,447 Posts
Default

Quote:
Originally Posted by akruppa View Post
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
xilman is offline   Reply With Quote
Old 2008-11-09, 07:45   #9
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

144638 Posts
Default

Quote:
Originally Posted by xilman View Post
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"?
davieddy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
What can you do with 2 prime numbers? VicDiesel Programming 12 2017-04-20 21:16
Right Perfect Prime Numbers Housemouse Math 34 2016-04-07 16:29
Prime Numbers Or Not Arxenar Miscellaneous Math 38 2013-06-28 23:26
All odd numbers are prime Citrix Lounge 5 2010-04-05 21:34
Old Gem Interview about prime numbers diep Lounge 3 2009-08-05 21:01

All times are UTC. The time now is 14:25.

Fri Oct 30 14:25:05 UTC 2020 up 50 days, 11:36, 2 users, load averages: 1.81, 1.73, 1.86

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.