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:
“Our basic ideas about how to parent are encrusted with deeply felt emotions and many myths. One of the myths of parenting is that it is always fun and games, joy and delight. Everyone who has been a parent will testify that it is also anxiety, strife, frustration, and even hostility. Thus most major parenting- education formats deal with parental emotions and attitudes and, to a greater or lesser extent, advocate that the emotional component is more important than the knowledge.”
—Bettye M. Caldwell (20th century)
“There is assuredly no more effectual method of clearing up one’s own mind on any subject than by talking it over, so to speak, with men of real power and grasp, who have considered it from a totally different point of view.”
—Thomas Henry Huxley (1825–95)