Continued Fraction Factorization Algorithm

A Prime Factorization Algorithm which uses Residues produced in the Continued Fraction of $\sqrt{mN}$ for some suitably chosen $m$ to obtain a Square Number. The Algorithm solves

$$x^2\equiv y^2\ \left({{\rm mod\ } {n}}\right)$$

by finding an $m$ for which $m^2$ (mod $n$) has the smallest upper bound. The method requires (by conjecture) about $\mathop{\rm exp}\nolimits (\sqrt{2\log n\log\log n}\,)$ 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 $F_7$.'' Math. Comput. 29, 183-205, 1975.

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