BACKGROUND Invented (presumably) by Monsieur Fermat himself. Haw, haw, haw.
Later improved by the big cheese... GAUSS!

---

BIG IDEA 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.

---

METHOD

1. Choose a number, N, you wish to factor
2. Is N a perfect square?
   • YES? - You found two factors! Take sqrt() and bail.
   • NO? - continue to next step
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

---

TECHNICAL ANALYSIS 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...

---

LINKS

• Time Analysis: See how well it works with certain numbers
• Source Code: Attempt this at home!
• Alternate Description

---

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