Editing Pollard's p − 1 algorithm (section)

==Base concepts==
Let ''n'' be a composite integer with prime factor ''p''.  By [[Fermat's little theorem]], we know that for all integers ''a'' coprime to ''p'' and for all positive integers ''K'':

:<math>a^{K(p-1)} \equiv 1\pmod{p}</math>

If a number ''x'' is congruent to 1 [[Modular arithmetic|modulo]] a factor of ''n'', then the {{nowrap|[[Greatest common divisor|gcd]](''x'' &minus; 1, ''n'')}} will be divisible by that factor.

The idea is to make the exponent a large multiple of ''p''&nbsp;&minus;&nbsp;1 by making it a number with very many prime factors; generally, we take the product of all prime powers less than some limit ''B''.  Start with a random ''x'', and repeatedly replace it by <math>x^w \bmod n</math> as ''w'' runs through those prime powers.  Check at each stage, or once at the end if you prefer, whether {{nowrap|gcd(''x'' &minus; 1, ''n'')}} is not equal to&nbsp;1.