Fermat's method works best when there's is a factor near the square-root of ''N''. Perhaps one can arrange for that to happen.
If one knewknows the approximate ratio of two factors (<math>d/c</math>), then one couldcan pick a rational number <math>v/u</math> near that value. <math>Nuv = cv * du</math>, and the factors are roughly equal: Fermat's, applied to ''Nuv'', will find them quickly. Then <math>gcd(N,cv)=c</math> and <math>gcd(N,du)=d</math>. (Unless ''c'' divides ''u'' or ''d'' divides ''v''.)
Generally, one doesn'tdoes not know the ratio, but one can try various <math>u/v</math> values, 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 <math>O(N^{1/3})</math> time.
See R. Lehman, "Factoring Large Integers", ''Mathematics of Computation'', 28:637-646, 1974.
