The Basic Method
One tries various values of a, hoping that is a square.
FermatFactor(N): // N should be odd a ← ceil(sqrt(N)) b2 ← a*a - N while b2 isn't a square: a ← a + 1 // equivalently: b2 ← b2 + 2*a + 1 b2 ← a*a - N // a ← a + 1 endwhile return a - sqrt(b2) // or a + sqrt(b2)For example, to factor, one computes
| a: | 78 | 79 | 80 |
|---|---|---|---|
| b2: | 125 | 282 | 441 |
The third try produces a square., and the factors are, and .
Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of a and b. That is, is the smallest factor ≥ the square-root of N. And so is the largest factor ≤ root-N. If the procedure finds, that shows that N is prime.
For, let c be the largest subroot factor., so the number of steps is approximately .
If N is prime (so that ), one needs steps! This is a bad way to prove primality. But if N has a factor close to its square-root, the method works quickly. More precisely, if c differs less than from the method requires only one step. Note, that this is independent of the size of N.
Read more about this topic: Fermat's Factorization Method
Famous quotes containing the words basic and/or method:
“It is not an exaggeration to say that play is as basic to your child’s total development as good food, cleanliness, and rest.”
—Joanne E. Oppenheim (20th century)
“Traditional scientific method has always been at the very best 20-20 hindsight. It’s good for seeing where you’ve been. It’s good for testing the truth of what you think you know, but it can’t tell you where you ought to go.”
—Robert M. Pirsig (b. 1928)