Williams' P + 1 Algorithm - Generalization

Generalization

Based on Pollard's p-1 and Williams' p+1 factoring algorithms, Eric Bach and Jeffrey Shallit developed techniques to factor n efficiently provided that is has a prime factor p such that any kth cyclotomic polynomial Φ_k(p) is smooth. The first few cyclotomic polynomials are given by the sequence Φ₁(p) = p-1, Φ₂(p) = p+1, Φ₃(p) = p2+p+1, and Φ₄(p) = p2+1.