A Prime Factorization Algorithm which uses Residues produced in the Continued Fraction of for some suitably chosen to obtain a Square
Number. The Algorithm solves

by finding an for which (mod ) has the smallest upper bound. The method requires (by conjecture) about steps, and was the fastest Prime Factorization Algorithm in use before the Quadratic Sieve Factorization Method, which eliminates the 2 under the Square Root (Pomerance 1996), was developed.

**References**

Morrison, M. A. and Brillhart, J. ``A Method of Factoring and the Factorization of .''
*Math. Comput.* **29**, 183-205, 1975.

Pomerance, C. ``A Tale of Two Sieves.'' *Not. Amer. Math. Soc.* **43**, 1473-1485, 1996.

© 1996-9

1999-05-26