P–1Dem

Pollard p − 1 Demonstration

Compute $\gcd(a^{k!}-1,n)$ one value of $k$ at a time

Composite number $n$:

Base $a$:

Maximum value of $k$:

Pollard p − 1 method

At step $k$, the current residue is $b_k\equiv a^{k!}\pmod n$. If a prime $p\mid n$ has $p-1\mid k!$, Fermat’s theorem gives $p\mid b_k-1$.

1. 1Begin with $b_0=a$.
2. 2Compute $b_k\equiv b_{k-1}^{k}\pmod n$, so $b_k\equiv a^{k!}\pmod n$.
3. 3Evaluate $g_k=\gcd(b_k-1,n)$.
4. 4Stop when $g_k>1$; it is useful when $1<g_k<n$.