Fermat's factorization method: Difference between revisions

Revision as of 19:04, 13 December 2007

Revision as of 13:45, 28 January 2008

Line 35:

==Fermat's and trial division==

Let's factor the prime number N=2345678917, but also compute B and A-B throughout. Going up from <math>\sqrt{N}</math>, we can tabulate:

<table>

<tr><td>A: </td><td>48433</td> <td>48434</td> <td>48435</td> <td>48436</td> </tr>

<tr><td>BsqB²:</td><td>76572</td> <td>173439</td> <td>270308</td> <td>367179</td> </tr>

<tr><td>B: </td><td>276.7</td> <td>416.5</td> <td>519.9</td> <td>605.9</td> </tr>

<tr><td>A-B: </td><td>48156.3</td><td>48017.5</td><td>47915.1</td><td>47830.1</td></tr>

</table>

Line 47 ⟶ 48:

Trial division would normally try up to 48432; but after only four Fermat steps, we need only divide up to 47830, to find a factor or prove primality.

This all suggests a combined factoring method. Choose some bound <math>c > \sqrt{N}</math>; use Fermat for factors between <math>\sqrt{N}</math> and <math>c</math>. This gives a bound for trial division which is <math>c - \sqrt{c^2 - N}</math>. In the above example, with <math>c = 48436</math> the bound for trial division is 47830. A reasonable choice could be <math>c = 55000</math> giving a bound of 28937.

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

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

<table>

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

Line 54 ⟶ 57:

<tr><td>A-B:</td><td>24582.9</td> <td>24582.2</td> </tr>

</table>

This all suggests a combined factoring method. Choose some bound ''c''; use trial division to find factors below ''c'', and Fermat's for factors above ''c''. That is, do Fermat until <math>a-b < c</math>, or <math>a > (c+N/c)/2</math>. The best choice of ''c'' depends on ''N'', and on the computing environment.

It also depends on the algorithm. There are ways to speed-up the basic method.

==Sieve improvement==