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:
“We are more thoroughly an enlightened people, with respect to our political interests, than perhaps any other under heaven. Every man among us reads, and is so easy in his circumstances as to have leisure for conversations of improvement and for acquiring information.”
—Benjamin Franklin (1706–1790)