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.

**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

1999-05-25