If the approximate ratio of two factors (<math>d/c</math>) is known, then a [[rational number]] <math>v/u</math> can be picked near that value. <math>Nuv = cv \cdot du</math>, and Fermat's method, applied to ''Nuv'', will find the factors <math>cv</math> and <math>du</math> quickly. Then <math>\gcd(N,cv)=c</math> and <math>\gcd(N,du)=d</math>. (Unless ''c'' divides ''u'' or ''d'' divides ''v''.)
Generally, if the ratio is not known, various <math>u/v</math> 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 <math>O(N^{1/3})</math> time.<ref>{{cite journal |authorlast=Lehman, |first=R. Sherman |year=1974 |title=Factoring Large Integers |journal=[[Mathematics of Computation]] |yeardoi=197410.2307/2005940 |doi-access=free |jstor=2005940 |volume=28 |issue=126 |pages=637–646 |url=https://www.ams.org/journals/mcom/1974-28-126/S0025-5718-1974-0340163-2/S0025-5718-1974-0340163-2.pdf |doi=10.2307/2005940 |jstor=2005940 |doi-access=free}}</ref>
==Other improvements==
Line 171:
==References==
*{{citation |last=Fermat |year=1894|title=Oeuvres de Fermat |volume=2 |page=256 |year=1894}}
