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

Greg Hewgill gregh at lightspeed.net
Tue Aug 18 20:30:11 EDT 1998


Eric Gindrup wrote:
>     The first is the Lucas-Lehmer test.  By itself, this test applied to
>     an odd number is pretty quick.  However, up around where GIMPS is
>     currently searching, there are a lot of composite odd numbers.

The LL test can only be applied to so-called "Mersenne" numbers. A Mersenne
number is a number of the form (2^p)-1 where p is a prime number. A
Mersenne number may or may not be prime; this is the question the LL test
is designed to answer.

>     The second is factorization of known "Mersenne composites".  I see a
>     reference to an Elliptic Curve factorization method on the GIMPS
>     site.  I *thought* they were using Number Field Sieve methods up
>     until very recently.  Anyway...

The factoring that is built-in to the GIMPS client is essentially brute
force trial factoring (we all know how that works :). For a given Mersenne
number (2^p)-1, its factors are _necessarily_ all of the form 2kp+1 where k
is an integer. Trial factoring basically just divides (2^p)-1 by 2kp+1 for
each value of k, checking to see whether there is a remainder. If it
divides evenly, we have a factor and the number isn't prime.

For a given Mersenne number, the GIMPS client will automatically do trial
factoring up to a certain limit. For a number with p in the 5.7M range,
factoring is performed for all possible factors up to 2^62. The upper bound
on factoring is calculated as tradeoff between trying small factors and
actually doing the LL test (which won't produce any factors if the number
is composite).

NFS and ECM are two other factoring methods that are both nondeterministic.
They can find larger factors than trial division in less time. But you're
not guaranteed to find such a factor unless you pick just the right
starting parameters.

>     The *slow* part is the division afterward to find out what's left
>     after the new factor is removed.


I think this is usually done by continuing to look for new factors in the
original number (which, being a Mersenne number, is often easier to work
with).

Greg Hewgill

--
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