mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Prime numbers (https://www.mersenneforum.org/showthread.php?t=4048)

Unregistered 2005-04-26 23:11

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

wblipp 2005-04-27 00:01

[QUOTE=Unregistered]Is it possible to get all known prime numbers? (We want to brute force 1024 bits RSA key)[/QUOTE]

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 2008-11-03 19:12

[QUOTE=wblipp;53789]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[/QUOTE]In principle it could be stored in a single hydrogen atom.

Think about it before I reveal the answer.


Paul

akruppa 2008-11-04 14:56

[QUOTE=xilman;147728]In principle it could be stored in a single hydrogen atom.

Think about it before I reveal the answer.

Paul[/QUOTE]

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 2008-11-07 15:25

[QUOTE=xilman;147728]In principle it could be stored in a single hydrogen atom.

Think about it before I reveal the answer.[/QUOTE]Naively we might try to encode all the possible values as a bitmap. Then consider the bitmap as a single large number with 2[sup]512[/sup] 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[sub]512[/sub] 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[sup]512[/sup]. So we store the log[sub]512[/sub](512), or simply 1. Where 1 means to generate all the primes up to 2[sup]512[sup]1[/sup][/sup]. If we were to store 2 in the hydrogen atom then instead we would generate primes up to 2[sup]512[sup]2[/sup][/sup].

CRGreathouse 2008-11-07 23:43

[QUOTE=xilman;147728]In principle it could be stored in a single hydrogen atom.

Think about it before I reveal the answer.[/QUOTE]

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 2008-11-08 10:11

[quote=Unregistered;53781]Is it possible to get all known prime numbers? (We want to brute force 1024 bits RSA key)[/quote]

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 [B]much, much, much[/B] larger keys that would ensure that your brute force attack would take a [B]very, very, very, long [/B]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 2008-11-08 18:05

[QUOTE=akruppa;147817]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[/QUOTE]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 [I]n[/I] but differing [I]l[/I] 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 2008-11-09 07:45

[quote=xilman;148389]
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[/quote]
Does this invoke the "quantum Zeno effect"?


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

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