Multiplier Improvement
Fermat's method works best when there is a factor near the square-root of N. Perhaps it can be arranged for that to happen.
If the approximate ratio of two factors is known, then the rational number can picked near that value., and the factors are roughly equal: Fermat's, applied to Nuv, will find them quickly. Then and . (Unless c divides u or d divides v.)
Generally, if the ratio is not known, various values can be tried, and try to factor each resulting Nuv. R. Lehman devised a systematic way to do this, so that Fermat's plus trial-division can factor N in time. See R. Lehman, "Factoring Large Integers", Mathematics of Computation, 28:637-646, 1974.
Read more about this topic: Fermat's Factorization Method
Famous quotes containing the word improvement:
“Unlike the normal pattern, I know I have grown more liberal as I’ve grown older. I have become more convinced that there is room for improvement in the world.”
—Walter Wellesley (Red)