Fermat's factorization method: Difference between revisions

Revision as of 05:01, 19 April 2006

Revision as of 05:02, 19 April 2006

Line 98:

Fermat's method works best when there's a factor near the square-root of ''N''. Perhaps one can arrange for that to happen.

If one knew the approximate ratio of two factors (<math>d/c</math>), then one could pick a rational number <math>u/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't 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.