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 |
P-1 factorization method
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
From the previous congruence we also get:
, where k is a non-negative integer. This means that
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.
Contents
[hide]Step 1
Suppose that the largest prime factor of p-1 is less than a bound B1. Then the method proceeds to compute
where
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
The Little Fermat Theorem states that
So computing
When factoring a number of the form
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
Also precompute the values
Let C be the previous multiple of 6 to B1.
Then we compute:
- ...
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:
multiplying by
So we compute
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:
(mod ) (mod ) (mod ) (mod ) (mod ) (mod ) (mod ) (mod )- gcd(
, ) = .
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.