Invented (presumably) by Monsieur Fermat himself. Haw, haw, haw.
Later improved by the big cheese... GAUSS!
This method is just like the primitive division algortihm, but rather than checking 2, 3, 5, ..., this method starts checking r = sqrt(N), then r-1, r-2, ... etc. But why would that work? Rememer that:

N = x^2 - y^2 implies N = (x+y)(x-y)
So, all we need to do is find such an x and y. Not so easy. What's the trick? Here's where Gauss stepped in:

The trick is to note the difference error, e = r^2 - N. You can use this to "quickly" skip over r-k's that don't minimize e enough. That's what Gauss figured out how to do. Very clever fellow.
  1. Choose a number, N, you wish to factor
  2. Is N a perfect square?
  3. Let r = sqrt(N), the integer square root.
  4. Compute e = r^2 - N, sometimes called "the residue"
  5. Let u = 2r + 1, and v = 1
  6. If e is zero, then we found a factor - namely (u-v)/2. If not...
  7. As long as e is negative, add u to e, then increment u by two
  8. As long as e is positive, subtract v from e, then increment v by two
  9. Go back to step 6

This algorithm works wonderfuly if either:
  1. N is small ( < 10,000,000 ), or...
  2. the factor(s) you are looking for are "close" to sqrt(N)
Note: "Close" is a relative notion. The larger N is, the more the word "close" looses its meaning. i.e. If N is of RSA magnitute, N could only have two very large factors, and yet have enough play room to make this algorithm go on searching for a long time.

Theoretical Runtime:
O( exp(# of digits in N) ) ...i think...


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

Paul Herman

Last Updated: May 23, 1997