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.
." Math. Comput. 29, 183-205, 1975.Pomerance,
C. "A Tale of Two Sieves." Not. Amer. Math. Soc. 43, 1473-1485,
1996.