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 [math]\displaystyle{ 2^p-1 }[/math] must be of the algebraic form [math]\displaystyle{ 2kp+1 }[/math] for some positive integer [math]\displaystyle{ k }[/math] and furthermore must also leave a remainder of either 1 or 7 upon division by 8. See below for an explanation.

A straightforward method of testing would be to check every possible number [math]\displaystyle{ n=2kp+1 }[/math] of a given maximum size which satisfies the division by 8 criterion to see if it is a factor of [math]\displaystyle{ 2^p-1 }[/math]. Long division is not an efficient way to do this, however! It is much easier to compute [math]\displaystyle{ 2^p\,\bmod n }[/math], i.e., the remainder after division by [math]\displaystyle{ n }[/math] by a "power-mod" algorithm, and then checking to see if the result is 1.

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 [math]\displaystyle{ n }[/math] which are prime. We can eliminate most composite values of [math]\displaystyle{ n }[/math] quite efficiently by a sieving process, in which a list of several thousand n values is examined by a single process. Every third value will be divisible by 3 and hence eliminated as composite. Next every fifth value will then be divisible by 5, and is eliminated if it was not previously eliminated in the divisibility by 3 test, and so forth. It is not necessary to carry this sieving process all the way to eliminate every last composite number, as it may actually be more efficient to test a few composite numbers than to eliminate them in the sieve. For example, if the sieving process eliminates 95% of the composite numbers, it may make more sense to test the remaining 5% along with any prime potential factors by the power-mod algorithm than to do further sieving.

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 [math]\displaystyle{ 2^{30030907}-1 }[/math] to see if it is prime, it has been trial factored up to the 68 bit level. The number 30030907 is called the exponent and you need to multiply 2 by 2 this many times then subtract 1 to see what this number actually looks like.

Constraints on prime factors of Mersenne numbers

• The prime factors of numbers of the form [math]\displaystyle{ 2^p-1 }[/math] where [math]\displaystyle{ p }[/math] is prime have the form [math]\displaystyle{ q = 2kp+1 }[/math].

From Fermat's theorem we have [math]\displaystyle{ 2^{q-1} \equiv 1\,\pmod q }[/math] (since [math]\displaystyle{ q }[/math] is prime).

From definition of Mersenne number we have [math]\displaystyle{ 2^p \equiv 1\,\pmod q }[/math] (since [math]\displaystyle{ q }[/math] is a divisor of the Mersenne number).

This means that [math]\displaystyle{ \gcd(p, q-1) \gt 1 }[/math]. Since [math]\displaystyle{ p }[/math] is prime, then [math]\displaystyle{ q-1 }[/math] must be multiple of [math]\displaystyle{ p }[/math]. Since [math]\displaystyle{ q-1 }[/math] is even, [math]\displaystyle{ q-1 }[/math] must be multiple of [math]\displaystyle{ 2p }[/math], so [math]\displaystyle{ q = 2kp+1 }[/math].

• The prime factors of numbers of the form [math]\displaystyle{ 2^p-1 }[/math] where [math]\displaystyle{ p }[/math] is prime have the form [math]\displaystyle{ q = 8k+1 }[/math] or [math]\displaystyle{ q = 8k+7 }[/math].

As was written in the previous paragraph, [math]\displaystyle{ 2^p \equiv 1\,\pmod q }[/math]. So [math]\displaystyle{ 2^{p+1} \equiv 2\,\pmod q }[/math]. Since [math]\displaystyle{ p+1 }[/math] is even, the number 2 is a quadratic residue modulo [math]\displaystyle{ q }[/math]. Using the law of quadratic reciprocity we find that [math]\displaystyle{ q\equiv 1\,\pmod 8 }[/math] or [math]\displaystyle{ q\equiv 7\,\pmod 8 }[/math].

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.