Pollard p-1 Factorization Method

A Prime Factorization Algorithm which can be implemented in a single-step or double-step form. In the single-step version, Primes $p$ are found if $p-1$ is a product of small Primes by finding an $m$ such that

$$m\equiv c^q\ \left({{\rm mod\ } {n}}\right),$$

where $p-1\vert q$, with $q$ a large number and $(c,n)=1$. Then since $p-1\vert q$, $m\equiv 1\ \left({{\rm mod\ } {p}}\right)$, so $p\vert m-1$. There is therefore a good chance that $n\notdiv m-1$, in which case $\mathop{\rm GCD}\nolimits (m-1,n)$ (where GCD is the Greatest Common Divisor) will be a nontrivial divisor of $n$.

In the double-step version, a Primes $p$ can be factored if $p-1$ is a product of small Primes and a single larger Prime.

See also Prime Factorization Algorithms, Williams p+1 Factorization Method

References

Bressoud, D. M. Factorization and Prime Testing. New York: Springer-Verlag, pp. 67-69, 1989.

Pollard, J. M. ``Theorems on Factorization and Primality Testing.'' Proc. Cambridge Phil. Soc. 76, 521-528, 1974.