Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Williams's p + 1 algorithm
open-in-new
<p>In <a href="/facts/Computational_number_theory/7Lu5N57C">computational number theory</a>, Williams's <i>p</i> + 1 algorithm is an <a href="/facts/Integer_factorization/EjMCTz2t">integer factorization</a> algorithm, one of the family of <a href="/facts/Algebraic-group_factorisation_algorithms/rtwGraLN">algebraic-group factorisation algorithms</a>. It was invented by <a href="/facts/Hugh_C._Williams/70ToIVyl">Hugh C. Williams</a> in 1982. </p><p>It works well if the number <i>N</i> to be factored contains one or more prime factors <i>p</i> such that <i>p</i> + 1 is <a href="/facts/Smooth_number/pC6DVLJW">smooth</a>, i.e. <i>p</i> + 1 contains only small factors. It uses <a href="/facts/Lucas_sequence/kceqhe6X">Lucas sequences</a> to perform exponentiation in a <a href="/facts/Quadratic_field/dUnSDN4e">quadratic field</a>. </p><p>It is analogous to <a href="/facts/Pollard%2527s_p_-_1_algorithm/dITySRp5">Pollard's <i>p</i> − 1 algorithm</a>. </p>