[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