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:
“The man who is admired for the ingenuity of his larceny is almost always rediscovering some earlier form of fraud. The basic forms are all known, have all been practicised. The manners of capitalism improve. The morals may not.”
—John Kenneth Galbraith (b. 1908)
“The method of authority will always govern the mass of mankind; and those who wield the various forms of organized force in the state will never be convinced that dangerous reasoning ought not to be suppressed in some way.”
—Charles Sanders Peirce (1839–1914)