It uses Lucas sequences to perform exponentiation in a quadratic field.
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
, 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.
, 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
To find the M-th element V of the sequence characterized by B, we proceed in a manner similar to left-to-right exponentiation: With N=112729 and A=5, successive values of
are: At this point, gcd(110229-2,112729) = 139, so 139 is a non-trivial factor of 112729.
is the lowest factorial which is multiple of 140, so the proper factor 139 is found in this step.
Using another initial value, say A = 9, we get: At this point gcd(91645-2,112729) = 811, so 811 is a non-trivial factor of 112729.
is the lowest factorial which is multiple of 810, so the proper factor 811 is found in this step.
The factor 139 is not found this time because p−1 = 138 = 2 × 3 × 23 which is not a divisor of 9!
As can be seen in these examples we do not know in advance whether the prime that will be found has a smooth p+1 or p−1.
Based on Pollard's p − 1 and Williams's p+1 factoring algorithms, Eric Bach and Jeffrey Shallit developed techniques to factor n efficiently provided that it has a prime factor p such that any kth cyclotomic polynomial Φk(p) is smooth.