Subject: Re: [stella] I can't find it From: Russ Perry Jr <slapdash@xxxxxxxxxxxx> Date: Mon, 11 Sep 2000 23:10:21 0500 
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 milliondecimaldigit 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 50digit 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 >> 128bit key, so if we got the same size team together, it would only take >> 2^(960128) 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   8479529729 slapdash@xxxxxxxxxxxx VIDEOGAME COLLECTOR!  ++================================================================*//  Archives (includes files) at http://www.biglist.com/lists/stella/archives/ Unsub & more at http://www.biglist.com/lists/stella/
Current Thread 


< Previous  Index  Next > 

Re: [stella] I can't find it, Andrew Davie  Thread  Re: [stella] I can't find it, Glenn Saunders 
RE: [stella] I can't find it, Russ Perry Jr  Date  Re: [stella] I can't find it, Glenn Saunders 
Month 