Jump to content

Williams's p + 1 algorithm

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Charles Matthews (talk | contribs) at 11:45, 25 May 2005 (copy edit). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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)

Template:Mathstub

Retrieved from "https://en.wikipedia.org/w/index.php?title=Williams%27s_p_%2B_1_algorithm&oldid=14207551"