Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
GIMPS factoring and sieving
Before a Lucas-Lehmer test is done on an exponent, it first undergoes trial factoring. If a factor is found, then the number is definitely composite, so a Lucas-Lehmer Test is unnecessary. It often takes much less effort to find a factor than to do the Lucas-Lehmer Test; in fact, over 60% of Mersenne numbers with prime exponents are eliminated from consideration as possible primes this way, so factoring is an important component of maximizing the work throughput of the GIMPS project.
The programs Prime95 (Windows version) and MPrime (Linux version) are capable of doing three different types of factoring: trial factoring, p-1 and ECM, but only the first two of these types are routinely done on GIMPS candidates.
Trial factoring
It consists of testing all possible factors of a given Mersenne number up to some predetermined size, usually a prescribed number of bits.
It is known that any factor of the Mersenne number
A straightforward method of testing would be to check every possible number
There is another shortcut which makes the test more efficient as well. Because the smallest factor (other than 1) of any number must be a prime number, we only have to check values of
When the number appears in the client's worktodo.ini file it will say something like this: Test=30030907,1,68. This means that the client is testing
Constraints on prime factors of Mersenne numbers
- The prime factors of numbers of the form
where is prime have the form .
- From Fermat's theorem we have
(since is prime). - From definition of Mersenne number we have
(since is a divisor of the Mersenne number). - This means that
. Since is prime, then must be multiple of . Since is even, must be multiple of , so .
- The prime factors of numbers of the form
where is prime have the form or .
- As was written in the previous paragraph,
. So . Since is even, the number 2 is a quadratic residue modulo . Using the law of quadratic reciprocity we find that or .
p-1
If a factor is not found by this trial factoring process, Prime95 or mprime then goes on to use a method called p-1 ("P minus one") factoring, originated by John Pollard in 1974, to search for larger factors. P-1 factoring consists of two stages, and factors may be found at the end of either stage. If a factor is found at the end of the first stage, the Mersenne prime candidate is eliminated, so the second stage is not done. Notice that step 2 requires a lot of memory but almost all factors found by p-1 are discovered in this step.
ECM
The program can also use a factoring process known as ECM, the elliptic curve method, invented in 1985 by Hendrik Lenstra. ECM is not routinely used on GIMPS candidates, mainly because a larger number of candidates can be eliminated in a given amount of time using P-1 factoring than with ECM. In the interests of efficiency of the overall project, P-1 makes more sense. Nevertheless, there are often larger factors that may be found more efficiently with ECM, and some participants enable ECM through the advanced menu to play with this factoring method. ECM is often used to try to factor Fermat numbers as well as smaller Mersenne numbers, such as the ones that are being attempted by the Cunningham project.
General |
Definitions |
Work with GIMPS |
Related |
FAQ |