Re: Looking at the stats...

Karl J. Runge (runge@redhook.llnl.gov)
Sat, 12 Apr 97 03:24:03 PDT


On Fri, 11 Apr 1997, Brett Moseley <brette@wam.umd.edu> wrote:

> Looking at the exponential growth in terms of keys found, anyone want to
> take a guess as to when we'll be done... I'm guessing in the three-four
> day range, although I guess the curve could flatten out...
>
> Any math majors want to hazard a more concrete guess? Its funny but the
> graphs remind me of some old Calc 1 problems...

Just to prove I can nerd out using numbers along with the best of 'em, I
tried to think how one could model the key-rate versus time.

Let r(t) be the key rate, the number of keys checked per day, and "t"
the time (i.e. which day).

One might model things by:

dr(t)/dt = a*r(t) + b

dr(t)/dt is the time derivative of the key rate. The amount the
key rate changes per day.

The a*r(t) term says:

Our key rate grows proportional to the current keyrate. This is
plausible given the rule people running will tell friends about DES
challenge, some of which will participate, and so on. This is
exponential growth.

The b term say:

Nah, our key rate grows at a constant rate. The number of machines
added per day is pretty much the same. This is linear growth.

In reality a better model would be to have the a and b depend on time.
I.e. a(t), b(t). One might say the a(t) and b(t) make big jumps after
important press releases, etc, etc: but this is impossible to model.

So let's keep a and b constant and try to get some estimates.

I considered the two cases:

1) a != 0 and b = 0 (expo growth)

2) b != 0 and a = 0 (linear growth)

Reasonable to guess the truth lies somewhere in between.

I took the data for the last 20 days and did a least squares fit
to the data for the two cases to get either "a" or "b".

My results (I might have a bug or two left, it's late and the wine
bottle over there looks surprisingly empty ;-)

1) expo growth: time to 1/2 keyspace: 95 days
time to full keyspace: 106 days.

if I fit to the last 30 days, I get full keyspace is done in 81 days
which is close to someone else's exponential growth estimate.

But doing 1/2 of the keyspace in the last 11 days sounds a bit much,
let's err on the side of conservative and look at

1) linear growth: time to 1/2 keyspace: 268 days
time to full keyspace: 378 days.

This is most likely an underestimate. But I think it is GREAT NEWS!
Worse case seems to be about one year right now! Some more good press
to jack up "b" and we'll be in great shape!

My speculation: 4-5 months from now, Aug-Sept.

But the more exponential the better! I hope I'm underestimating!

Best,

Karl