= Pollard's p-1 algorithm
{c}
{wiki=Pollard's_p_−_1_algorithm}
For an <integer> $n$ to be factored, <John Pollard>'s method chooses an <integer> $a$ <coprime> to $n$ and an <exponent> $M$ divisible by many small <prime powers>. Compute $d=\gcd(a^M-1,n)$ by <modular exponentiation> and the <Euclidean algorithm>. If $1<d<n$, it is a proper <factor>. If a <prime divisor> $p$ of $n$ has $p-1\mid M$, <Fermat's little theorem> ensures $p\mid d$; success requires some other <prime divisor> not to divide $a^M-1$. Common choices are $M=B!$ and $M=\operatorname{lcm}(1,\ldots,B)$. The method exploits a smooth $p-1$, rather than a small <factor> $p$ itself.
Back to article page
