Williams's p + 1 algorithm

In computational number theory, Williams' p + 1 algorithm is an integer factorization algorithm invented by H. C. Williams.

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.

It is analogous to Pollard's p-1 algorithm.

Reference

H.C. Williams, A p+1 method of factoring, Math. Comp., 39, 225-234 (1982)

External links

• http://www.mersennewiki.org/index.php/P_Plus_1 MersenneWiki article about p+1 factorization method.