## Continued Fraction Factorization Algorithm

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.

See also Exponent Vector, Prime Factorization Algorithms

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 Eric W. Weisstein
1999-05-26