Fermat's factorization method: Difference between revisions

Revision as of 05:02, 19 April 2006

Revision as of 05:04, 19 April 2006

Line 49:

In this regard, Fermat's gives diminishing returns. One would probably stop long before this point:

<table>

<tr><td>A: </td><td>60001</td> <td>6000260001</td> </tr>

<tr><td>Bsq:</td><td>1254441084</td><td>1254561087</td></tr>

<tr><td>B: </td><td>35418.1</td> <td>35419.8</td> </tr>

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>v/u/v</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.