about Lucas-Lehmer test and Prime 95

[ColdFury]

For example, I use a 2048-bit key for my sshd session... If I'm thinking about this right that key should be impossible to crack, right?

I mean, RC5 took forever to crack 64 bits, right?

RC5 is a symmetric algorithm, there's no known faster way than to try a brute force.

RSA isn't a symmetric algorithm. To "break" the key, you just need to factor the 2048 bit number. There are a variety of ways to do this, trial factoring being the slowest.

You could say the "value of a bit" is smaller in RSA than in symmetric algorithms.

[nomadicus]

Originally Posted by cheesehead

The entire universe could TF a number no larger than 2^2800. (Using our current trial-factoring methods and optimizations, that is.)

I actually understand this!

Thanks cheesehead, that kind of puts things in perspective.

So when I TF M19435217 to 67 bits (let's say that takes prime95 24 hours), I might have found a factor at 68 to 70 bits by waiting 2 to 8 extra days but the odds are against it.

To TF to 80 bits increases my odds of finding a factor but only if I were really, really patient -- as in wait a couple of decades.
Even then the payoff would most likely be "no factor found." (80 < sqrt(19435217)).

So a TF to 83 bits would not happen in my lifetime.

So let's see if I have things in perspective. My lifetime expectancy can be measured in TF bits which is something less then 83 bits. And the odds are that my TF lifetime accomplishment will be "no factor found."

More to the point, since I am 45, I might live another 81 bits and my epitaph should say "no factor found."

Where else, except for GIMPS, can I find such great information about myself???

-=- john

[jocelynl]

woohoo john,

I want some of that stuff you`re taking man.

joss

[cheesehead]

Originally Posted by nomadicus

So a TF to 83 bits would not happen in my lifetime.

But remember Moore's Law: The speed of CPUs doubles every 18 months. Also, recently Mr. Moore said it's now more like 14 months between doublings.

Each doubling increases your lifeTFtime by another bit!

since I am 45,

If you live another 35 years = 420 months, and CPU speeds double every 14 months, then you'd see your lifeTFtime increase from 83 to 113 bits!!

my epitaph should say "no factor found."

That's deep ... really deep.

[nomadicus]

Originally Posted by cheesehead

But remember Moore's Law:

Moore's Law is not about doubling speed, rather the doubling of transistors on an integrated circuit.
Regardless, I really like the idea that I should make it past 100 bits old. Who knows what technology holds in the future? 113 bits (plus or minus) gives me something to look forward to. :D

[smh]

Don't forget that we'll be testing much larger numbers by that time.

This will give you a couple of extra bits

[cheesehead]

Originally Posted by nomadicus

Moore's Law is not about doubling speed, rather the doubling of transistors on an integrated circuit.

Oh, that's right. Moore's Law is not even a quote of Gordon Moore -- it was originally stated by someone who read Moore's 1965 paper, where what Moore actually wrote was:

Originally Posted by Gordon Moore

The complexity [of integrated circuits] for minimum component costs has increased at a rate of roughly a factor of two per year

In 1975 Mr. Moore revised this from doubling every year to doubling every two years. "David House, an Intel executive at the time, noted that the changes would cause computer performance to double every 18 months." ("Moore's Law to roll on for another decade" - CNET News February 10, 2003)

So it's really "House's Law" that many (including me) often quote as Moore's Law.

By the way, "Forget Moore's Law", an essay by Michael S. Malone at Red Herring has an interesting take. If he's right, we might not see that 113-bit TF anyway because Intel et al. will stop turning out faster-and-faster CPUs before then.

[Axel Fox]

You're quite right, Cheesehead.

I don't know the exact boundary, but both Intel and AMD are closing to the absolute limit of modern CPUs because of the limits of the structure and architecture modern computers are based on. Intel and AMD engineers are already working on a completely new way to make CPUs and new architectures.

The only problem is making this new "CPU system" (preferrably even backward) compatible with the current CPUs.

The same thing is also happening with HDDs, it's almost impossible to make the magnetic surfaces even smaller without drastically increasing the risk of losing magnetisation. For this there are however already prototypes being tested. Don't know exactly how it worked anymore, but I read it in an article of a local Scientific Magazine (something like Scientific American, but in Dutch).

Axel Fox.

[cheesehead]

Originally Posted by Axel Fox

You're quite right, Cheesehead.

I don't know the exact boundary, but both Intel and AMD are closing to the absolute limit of modern CPUs because of the limits of the structure and architecture modern computers are based on. Intel and AMD engineers are already working on a completely new way to make CPUs and new architectures.

But did you read Michael S. Malone's article? It's at http://www.redherring.com/insider/2003/02/moore021003.html

If Malone is right, Intel/AMD won't get near that limit you mention, or at least their progress will greatly slow long before that limit, regardless of new architecture or way to make CPUs, for non-engineering reasons.

[cheesehead]

OTOH, once nanotechnology gets going, one of the obvious early applications would be to have nanobots make the circuits. With precision placement of individual atoms, bypassing shadow mask limitations, it might be feasible to rapidly skip several orders of magnitude in (performance per cost).

[Axel Fox]

Thx for the link to the article, Cheesehead. I found it very interesting and had not read it.