View source for P-1 factorization method

'''P-1''' is a [[:Category:Factorization|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 <math>a^{p-1}\equiv 1 \mbox{( mod } p)</math>.

From the previous congruence we also get:

:<math>a^{k(p-1)}\equiv 1</math>, where ''k'' is a non-negative integer. This means that <math>a^{k(p-1)} - 1</math>

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 <math>a^E\,\pmod{N}</math> where ''N'' is the number to factor.

:<math>E = 2^{E_2} * 3^{E_3} * 5^{E_5} * ... * B</math>

where <math>E_2</math> is selected so that <math>2^{E_2}</math> 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 <math>\sqrt{B1}</math>, ''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 <math>a^{p-1}\equiv 1\,\pmod {p}</math>. Since ''E'' is multiple of ''p-1'' we get <math>a^E\equiv 1\,\pmod {p}</math>. This means that <math>a^E-1</math> will be multiple of ''p'' but not of ''N'' (in general).

So computing <math>\gcd(a^E-1,\,N)</math> we will get a proper factor of ''N''.

When factoring a number of the form <math>2^p-1</math> (as in [[GIMPS]]) its prime factors have the form <math>2kp+1</math>, so the value ''p'' must always be a factor of ''E''. In this case the value of ''a'' must not be 2, because <math>2^E\equiv 1\,\pmod {N}</math>, so <math>\gcd(2^E - 1, \,N) = N</math>, 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 <math>F\equiv a^E\,\pmod N</math> be the output of the step 1.

Also precompute the values <math>S\equiv F^2\,\pmod N</math> and <math>H\equiv F^6\,\pmod N</math>.

Let ''C'' be the previous multiple of 6 to B1.

Then we compute:
:<math>Z_1\equiv F^{C+1}\,\pmod N</math>
:<math>Z_2\equiv F^{C+7}\equiv Z_1 * H\,\pmod N</math>
:<math>Z_3\equiv F^{C+13}\equiv Z_2 * H\,\pmod N</math>
:<math>Z_4\equiv F^{C+19}\equiv Z_3 * H\,\pmod N</math>
:...
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:
:<math>F^{C+5}\equiv 1\,\pmod p</math>
multiplying by <math>F^2</math> we get
:<math>Z_2\equiv F^{C+7}\equiv S\,\pmod p</math>
So we compute <math>Z\equiv (Z_1-1)(Z_2-1)(Z_2-S)(Z_3-1)(Z_3-S)(Z_4-1)(Z_4-S)...\pmod N</math> and finally gcd(''Z'', ''N'') will reveal a proper factor of ''N''.

===Example===
Suppose we want to find a factor of 2<sup>29</sup>-1 with B1 = 10.

Then E = 2<sup>3</sup> &times; 3<sup>2</sup> &times; 5 &times; 7 &times; 29.

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

Let a = 3. So the steps are:
:<math>3^2\equiv 9</math> (mod <math>2^{29} - 1</math>)
:<math>9^2\equiv 81</math> (mod <math>2^{29} - 1</math>)
:<math>81^2\equiv 6561</math> (mod <math>2^{29} - 1</math>)
:<math>6561^3\equiv 35437295</math> (mod <math>2^{29} - 1</math>)
:<math>35437295^3\equiv 518991192</math> (mod <math>2^{29} - 1</math>)
:<math>518991192^5\equiv 142236746</math> (mod <math>2^{29} - 1</math>)
:<math>142236746^7\equiv 237876521</math> (mod <math>2^{29} - 1</math>)
:<math>237876521^{29}\equiv 171331425</math> (mod <math>2^{29} - 1</math>)
:gcd(<math>171331425-1</math>,<math>2^{29}-1</math>) = <math>486737</math>.

So 2<sup>29</sup> - 1 = 486737 &times; 1103.

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

For [[GIMPS]], where the [[exponent]]s are very high, the values of B1 are selected above 1,000,000.

==See Also==
*[[Brent-Suyama extension]]
[[Category:Factorization]]