Williams' p + 1 algorithm

In computational number theory, Williams' p + 1 algorithm is an integer factorization algorithm, one of the family of algebraic-group factorisation algorithms. It was invented by Hugh C. Williams in 1982.

It works well if the number N to be factored contains one or more prime factors p such that p + 1 is smooth, i.e. p + 1 contains only small factors. It uses Lucas sequences to perform exponentiation in a quadratic field.

It is analogous to Pollard's p − 1 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 ${\displaystyle \gcd(N,V_{M}-2)}$ whenever M is a multiple of ${\displaystyle p-(D/p)}$, where ${\displaystyle D=A^{2}-4}$ and ${\displaystyle (D/p)}$ is the Jacobi symbol.

...
Wikipedia