Williams' P + 1 Algorithm - Algorithm

Algorithm

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

where all operations are performed modulo N.

Then any odd prime p divides whenever M is a multiple of, where and is the Jacobi symbol.

We require that, 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, this algorithm degenerates into a slow version of Pollard's p − 1 algorithm.

So, for different values of M we calculate, 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 is the M-th value of the sequence characterized by .

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