Re: [stella] I can't find it

Subject: Re: [stella] I can't find it
From: Russ Perry Jr <slapdash@xxxxxxxxxxxx>
Date: Sun, 17 Sep 2000 12:39:36 -0500
At 2:34 PM -0230 9/17/00, Julian Squires wrote:
>On Mon, Sep 11, 2000 at 11:10:21PM -0500, Russ Perry Jr wrote:
>> Sadly, there's no way to assume that the numbers used for the 7800 were
>> of Mersenne form, is there?  Or can we, just because they were able to
>> make primes of a sufficient size to begin with?

>It is extremely doubtful they were Mersenne primes.

So it's just as easy to find any prime of the size we're talking?

>> Up to 200 digits sounds right up our alley, but I guess it's the
>> supercomputer that stops us?

>It would take quite a while, even with the supercomputer. 200 digits
>is ~664 bits, right? 768-bits has been done before, iirc. It takes
>a long time and a lot of hardware, however.

Yeah, and this is actually 960 bits IIRC.

>Generating primes is trivial - there are infinitely many primes,
>and a hell of a lot of the size we want. Using a list offers no
>benefit for this size of number - the list would be /massive/.

Yeah, I realize, which is why I was wondering if there were other
ways we could cut that space down.

>> if they found two huge primes to multiply
>> together, doesn't that imply that they're "special" primes in some way?


So primes of that many digits really ARE easy to find?  I thought that
was another tricky math problem in itself...

>> Also, is there anything about how "robust" a number is that suggest we
>> needn't even bother checking numbers less than, say 100 digits, or might
>> they have thrown in a 50-digit number just to be coy?

>Working heuristically would tend not to pay off, as it is likely they
>just generated two large random primes of the appropriate size, which
>is the usual way of doing these things.

What I was asking above is essentially "what IS appropriate size?".  I
mean, under 50 digits isn't likely, is it?

Correct me if I'm wrong, but if you have two numbers, one X digits long
and the other Y digits, then their product is X+Y-[0|1] digits long,
right?  If we know "appropriate size", it gives us another bound as to
the size of the multiplicands.

>Setting a well-established algorithm against it would be better.

Indeed, but no one's found any programs to do just that.  We'd like to
be able to drop in our number and start it parsing.

>128-bit symmetric keys are not the same as 128-bit asymmetric keys.
>There are completely different principles behind symmetric and asymmetric
>systems. You can't generalize the time taken to attack one into the
>time to attack another.

Okay, but which is this key likely to be?  We're talking 1983-5 or so,
and in a commercial application.  Does that mean it's most likely

>Also, do you know how long 2^832 weeks is? I'll give you a hint, you
>won't be finishing anytime during the lifespan of the earth.

No one can pictures numbers that high, generally speaking, but of course
I recognize that it's obscenely large.

>A distributed effort for this would definitely be neat, but realize
>it's a huge effort, and probably isn't accessable at the moment.

How so -- just due to the size of the number?  Otherwise I don't see it
as intractable, but only very unlikely that we'd find it unless there's
some speedup in method or hardware & software.

>Perhaps there is a possibility with TWINKLE, Shamir's neat optical
>factoring box? (I don't know anything about it, except that it hasn't
>actually been constructed yet, so I don't know if it fits - although
>I believe it is still impractical for keys larger than 512 bits)

I'm not familiar with TWINKLE...  Is it basically a way to put the
factorization into an analog computing paradigm using light, or is
it actually a first stab at quantum computing?
||  Russ Perry Jr   2175 S Tonne Dr #105   Arlington Hts IL 60005  ||
||  847-952-9729    slapdash@xxxxxxxxxxxx    VIDEOGAME COLLECTOR!  ||

Archives (includes files) at
Unsub & more at

Current Thread