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, 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.