A variant of the Pollard p-1 method which uses Lucas sequences to achieve rapid factorization if some factor of has a decomposition of in small prime factors.
Williams p+1 Factorization Method
See also
Lucas Sequence, Pollard p-1 Method, Prime Factorization AlgorithmsExplore with Wolfram|Alpha
References
Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, p. 177, 1994.Williams, H. C. "A Method of Factoring." Math. Comput. 39, 225-234, 1982.Referenced on Wolfram|Alpha
Williams p+1 Factorization MethodCite this as:
Weisstein, Eric W. "Williams p+1 Factorization Method." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/WilliamspPlus1FactorizationMethod.html