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 AlgorithmsExplore with Wolfram|Alpha
WolframAlpha
More things to try:
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 AlgorithmCite this as:
Weisstein, Eric W. "Continued Fraction Factorization Algorithm." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ContinuedFractionFactorizationAlgorithm.html