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:
“Nothing and no one can destroy the Chinese people. They are relentless survivors. They are the oldest civilized people on earth. Their civilization passes through phases but its basic characteristics remain the same. They yield, they bend to the wind, but they never break.”
—Pearl S. Buck (1892–1973)
“The method of painting is the natural growth out of a need. I want to express my feelings rather than illustrate them. Technique is just a means of arriving at a statement.... I can control the flow of paint: there is no accident, just as there is no beginning and no end.”
—Jackson Pollock (1912–1956)