TOPICS
Search

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=y^2 (mod n)

by finding an m for which m^2 (mod n) has the smallest upper bound. The method requires (by conjecture) about exp(sqrt(2lnnlnlnn)) 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.


See also

Exponent Vector, Prime Factorization Algorithms

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Continued Fraction Factorization Algorithm

Cite this as:

Weisstein, Eric W. "Continued Fraction Factorization Algorithm." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ContinuedFractionFactorizationAlgorithm.html

Subject classifications