Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3).
Navigation
Topics Help • Register • News • History • How to • Sequences statistics • Template prototypes

P-1 factorization method

From Prime-Wiki
Jump to: navigation, search

P-1 is a factorization method invented by John Pollard in 1974.

It is based in the Fermat's Little Theorem that states that:

Let p be a prime which does not divide the integer a, then ap11( mod p).

From the previous congruence we also get:

ak(p1)1, where k is a non-negative integer. This means that ak(p1)1

is multiple of p.

Let p be a prime divisor of the number N to be factored. If we somehow find a multiple of p-1 we will find a multiple of p which (in general) will not be also a multiple of N, so a greatest common divisor operation will reveal the prime divisor.

Step 1

Suppose that the largest prime factor of p-1 is less than a bound B1. Then the method proceeds to compute aE(modN) where N is the number to factor.

E=2E23E35E5...B

where E2 is selected so that 2E2 is about B1 and the same for the other prime numbers. B is the greatest prime number less than or equal to B1.

In general, the number E should be multiple of p-1 because it is multiple of all prime factors of p-1. Notice that when p-1 has a repeated prime factor greater than B1, E will not be multiple of p-1 and the method fails, but this happens with a very low probability.

The Little Fermat Theorem states that ap11(modp). Since E is multiple of p-1 we get aE1(modp). This means that aE1 will be multiple of p but not of N (in general).

So computing gcd(aE1,N) we will get a proper factor of N.

When factoring a number of the form 2p1 (as in GIMPS) its prime factors have the form 2kp+1, so the value p must always be a factor of E. In this case the value of a must not be 2, because 2E1(modN), so gcd(2E1,N)=N, which is a trivial factor of N.

Step 2

Most of the composite numbers have a prime factor much greater than the other prime factors. Suppose that all prime factors of p-1 are less than the bound B1 except for one prime factor which is in the range B1 to B2. In this case step 1 will not succeed and thus it will not reveal a factor of N.

Let FaE(modN) be the output of the step 1.

Also precompute the values SF2(modN) and HF6(modN).

Let C be the previous multiple of 6 to B1.

Then we compute:

Z1FC+1(modN)
Z2FC+7Z1H(modN)
Z3FC+13Z2H(modN)
Z4FC+19Z3H(modN)
...

and so on until the exponent reaches B2. Since there is a prime factor of p-1 in the range B1 to B2, there is one value computed that must be congruent to 1 (mod p). This does not cover the case that the factor has the form C+5, C+11, C+17, i.e. congruent to 5 modulo 6. In the first case we have:

FC+51(modp)

multiplying by F2 we get

Z2FC+7S(modp)

So we compute Z(Z11)(Z21)(Z2S)(Z31)(Z3S)(Z41)(Z4S)...(modN) and finally gcd(Z, N) will reveal a proper factor of N.

Example

Suppose we want to find a factor of 229-1 with B1 = 10.

Then E = 23 × 32 × 5 × 7 × 29.

The number 29 was included as indicated on the last paragraph in Step 1.

Let a = 3. So the steps are:

329 (mod 2291)
9281 (mod 2291)
8126561 (mod 2291)
6561335437295 (mod 2291)
354372953518991192 (mod 2291)
5189911925142236746 (mod 2291)
1422367467237876521 (mod 2291)
23787652129171331425 (mod 2291)
gcd(1713314251,2291) = 486737.

So 229 - 1 = 486737 × 1103.

Notice that the factor found is composite. This normally occurs when B1 is too high (10 in this case).

For GIMPS, where the exponents are very high, the values of B1 are selected above 1,000,000.

See Also