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:
“... in Northern Ireland, if you don’t have basic Christianity, rather than merely religion, all you get out of the experience of living is bitterness.”
—Bernadette Devlin (b. 1947)
“Protestantism has the method of Jesus with His secret too much left out of mind; Catholicism has His secret with His method too much left out of mind; neither has His unerring balance, His intuition, His sweet reasonableness. But both have hold of a great truth, and get from it a great power.”
—Matthew Arnold (1822–1888)