[RC5]V3...Lets beat the GIMPS effort

Jeff Woods jwoods at delta.com
Tue Aug 18 18:20:24 EDT 1998


At 11:06 AM 8/18/98 -0600, you wrote:

>Another issue is well, how will this work.  My P2-266 can crunch a prime
>number in about 2 weeks.  Now, I know that's going to be unappealing to
>people and hopefully d.net will break that up into smaller chunks. 

Cannot be done.   The Mersenne test for numbers in the form of (2^p)-1 is
recursive, performing "p minus four" iterations of the test.  The starting
value for given iteration "x" is the final result of iteration x-1.   You
cannot do a given iteration without the one prior to it having been
completed.  It is a linear process.  A single Mersenne test cannot be
distributed the way a brute force keyspace attack can be.  It COULD be
distributed, with the result of iteration x being sent back to the key
server, with iteration x+1 being done by someone else, but what a waste of
time!   Better to just let one machine crunch out the full test of p-4
iterations.   

It is only that LAST iteration, where if the remainder is ZERO, that one
can tell if the candidate is a prime number, and since each depends on the
one before it....   And since as P grows, the task grows ENORMOUSLY,
greater than linearly, since the operation of an iteration includes a VERY
large multiplication and a squaring of the last result.... For P near
4,000,000, which is where GIMPS are now, that means Fast Fourier Transforms
(FFT's) with a 256 KB FFT table.   As P grows, so does the size of the FFT
table, making each "iteration" longer than for a smaller P.   So while the
number of iteration grows linearly, the length of each iteration ALSO
increases as P does, roughly on a quadratic scale.   

This has been well debated on the GIMPS list.... It just isn't possible to
distribute a given Lucas-Lehmer Mersenne test amongst multiple computers.
About all d.net could bring to the table is 25,000 computers, each taking
2-3 weeks per complete test.


--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list