## 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 are found if is a product of small Primes by finding an such that

where , with a large number and . Then since , , so . There is therefore a good chance that , in which case (where GCD is the Greatest Common Divisor) will be a nontrivial divisor of .

In the double-step version, a Primes can be factored if 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.

© 1996-9 Eric W. Weisstein
1999-05-25