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:
“They act as if they supposed that to be very sanguine about the general improvement of mankind is a virtue that relieves them from taking trouble about any improvement in particular.”
—John Morley [1st Viscount Morley Of Blackburn] (1838–1923)