Williams's p + 1 algorithm

In computational number theory, Williams' p + 1 algorithm is an integer factorization algorithm invented by H. C. Williams.

It works well if the number N to be factored contains one or more prime factors p such that

p + 1

is smooth, i.e. p + 1 contains only small factors. It uses Lucas sequences.

It is analogous to Pollard's p-1 algorithm.

The algorithm:

Choose some integer A greater than 2 which characterizes the sequence:

$V_{0}=2,V_{1}=A,V_{j}=AV_{j-1}-V_{j-2}$

where all operations are performed modulo N.

Then any odd prime p divides $\gcd(N,V_{M}-2)$ whenever M is a multiple of $p-(D/p)$, where $D=A^{2}-4$ and $(D/p)$ is the Jacobi symbol.

We require that $(D/p)=-1$, that is, D should be a quadratic non-residue modulo p. But as we don't know p beforehand, more than one value of A may be required before finding a solution. If $(D/p)=+1$, this algorithm degenerates into a slow version of Pollard's p-1 algorithm.

So, for different values of M we calculate $\gcd(N,V_{M}-2)$, and when the result is not equal to 1 or to N, we have found a non-trivial factor of N.

The values of M used are successive factorials, and $V_{M}$ is the M-th value of the sequence characterized by $V_{M-1}$.

To find the M-th element V of the sequence characterized by B, we proceed in a manner similar to left-to-right exponentiation:

 x=B           
 y=(B^2-2) mod N     
 for each bit of M to the right of the most significant bit
   if the bit is 1
     x=(x*y-B) mod N 
     y=(y^2-2) mod N 
   else
     y=(x*y-B) mod N 
     x=(x^2-2) mod N 
 V=x

An example:

With N=11111 and A=5, successive values of $V_{M}$ are:

 V1 of seq(5) = V1! of seq(5) = 5
 V2 of seq(5) = V2! of seq(5) = 23
 V3 of seq(23) = V3! of seq(5) = 987
 V4 of seq(987) = V4! of seq(5) = 662
 V5 of seq(662) = V5! of seq(5) = 10703

At this point, gcd(10703-2,11111) = 41, so 41 is a non-trivial factor of 11111.

Reference

H.C. Williams, A p+1 method of factoring, Math. Comp., 39, 225-234 (1982)

External links

• http://www.mersennewiki.org/index.php/P_Plus_1 MersenneWiki article about p+1 factorization method.