A prime factorization algorithm which uses residues produced in the continued fraction of sqrt(m N) for some suitably chosen m to obtain a square number. The algorithm solves x^2 congruent 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(2ln n ln ln n)) steps, and was the fastest prime factorization algorithm in use before the quadratic sieve, which eliminates the 2 under the square root, was developed.

exponent vector | prime factorization algorithms