Williams's p + 1 algorithm

Williams's p + 1 algorithm is an integer factorization algorithm from computational number theory, invented by Hugh C. Williams in 1982 and belonging to the family of algebraic-group factorisation methods. It works well when the number N being factored has a prime factor p for which p + 1 is smooth, meaning that it contains only small prime factors. It uses Lucas sequences to carry out exponentiation in a quadratic field, computing terms for successive factorials and taking the greatest common divisor of N with a term minus 2; a result other than 1 or N is a non-trivial factor. It is analogous to Pollard's p - 1 algorithm, and when p - 1 rather than p + 1 happens to be smooth it degenerates into a slow version of that method, which happens about half the time for a given choice of the starting integer, so several starting values may need trying. A second-stage continuation relaxes the condition so that one larger prime factor of p + 1 is allowed. Eric Bach and Jeffrey Shallit later generalised both methods to cyclotomic polynomials.