BACKGROUND
Developed (i think) in 1975 by M.A.Morrison and J.Brillhart.

This algorithm uses residues (or "the remainder modulo N") from the integer sqrt() function, just like in Fermat's method. A way to find integer square roots is to use continued fractions.

This was the fastest algorithm before the Quadratic Sieve method took over.
BIG IDEA
Choose an m such that m*N is a square number. Produce the continued fraction for sqrt(m*N). Solve:
x^2 = y^2 (mod N)
By finding an m for which m^2 (mod N) has the smallest upper bound. Right now, this makes no sense, as I just copied it from somewhere else. As soon as I read up some more on it, I will post it here.
METHOD
  1. Choose the number, N, you wish to factor
  2. Factor N
  3. Done! (mod details)
TECHNICAL ANALYSIS
Theoretical Runtime:
O( exp(sqrt( 2*ln(n)*ln(ln(n)))) )
LINKS

Back to the factoring theory page
Back to the factoring page
Back to my home page
Back to the pslc home page

Paul Herman
pherman@frenchfries.net

Last Updated: May 23, 1997