At 2:30 PM +1000 9/12/00, Andrew Davie wrote:
>I wrote to George Woltman regarding this - George is the head honcho in
>charge of GIMPS - the great internet mersenne prime search
>(www.entropia.com/primenet). Mersenne primes are of the form (2^p) - 1, and
>they are dealing with million-decimal-digit primes these days.
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?
>George was kind enough to respond, but unfortunately quenched my hope.
>I copy his email verbatim... we need a different approach :)
[George wrote:]
>You won't be able to factor it. The best known factoring algorithm at
>present is the Number Field Sieve (NFS). Using current computers it can
>crack numbers up to roughly 200 digits. That's using a distributed
>approach to run the sieve and a supercomputer to run the final step.
Up to 200 digits sounds right up our alley, but I guess it's the
supercomputer that stops us?
>The suggestion of factoring it by brute force by dividing up the
>key space would take eons.
This is a bit of what I feared... My post was slightly tongue in cheek,
as you might have noticed. Suggesting that we could cut out certain
combinations isn't trivial though... It does cut down the space quite
a bit, but just not in a big enough way. If it cuts it down to 10% of
a really large space, it's still a really large space. :-(
>The poster that thought he would get a list of known large primes
>doesn't understand how this number was constructed. It is not done
>using a list of known 130 digit primes. My PC can find 2 130 digit
>primes in less than a second.
I'm not sure I understand George here... I didn't mean to imply that
there was this list out there that Atari used, but if there were lists
of all primes up to certain point, it could be used to cut down the
key space quicker.
His answer kind of implies one thing that I was asking if we knew about
the number to be factored -- if they found two huge primes to multiply
together, doesn't that imply that they're "special" primes in some way?
Another thing... Not that it'll cut down the key space any, but if
you're looking for factors in a brute force way, you start at the square
root of the number and go down, right?
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?
"Rob" <kudla@xxxxxxxxx> wrote:
>> At 09:13 PM 9/11/00 -0500, Russ Perry Jr wrote:
>> >More seriously, perhaps a distributed computing effort like the RSA/DES
>> >challenges or SETI would work? Break the keyspace up into all numbers
>> Well, it took a distributed team a couple weeks last year to crack a
>> 128-bit key, so if we got the same size team together, it would only take
>> 2^(960-128) weeks to crack this one.... right?
Heh, I don't know if your math or method is right, but that's the kind of
number that was scaring me about this whole thing.
On the other hand, if it's going to take decades to crack, the sooner we
get started the better. ;-)
And if they come up with a better method in the meantime, then we only
wasted CPU cycles that were being wasted anyway, right? And hell, keep
in mind that some of the DES challenges took less time than they should
have because they lucked out and hit the correct combos early in the key
space. We might be so lucky as well.
--
//*================================================================++
|| Russ Perry Jr 2175 S Tonne Dr #105 Arlington Hts IL 60005 ||
|| 847-952-9729 slapdash@xxxxxxxxxxxx VIDEOGAME COLLECTOR! ||
++================================================================*//
--
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
