Fermat's factorization method: Difference between revisions

Revision as of 22:35, 26 May 2009

Revision as of 22:42, 26 May 2009

Line 10:

==The basic method==

One tries various values of ''a'', hoping that <math>a^2-N = b^2</math> is a square (note that variable b2 represents <math>b^2</math>).

:FermatFactor(N): // N should be odd

Line 43:

==Fermat's and trial division==

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

<table>

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

<tr><td>Bsqb2: </td><td>76572</td> <td>173439</td> <td>270308</td> <td>367179</td> </tr>

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

<tr><td>Aa-Bb: </td><td>48156.3</td><td>48017.5</td><td>47915.1</td><td>47830.1</td></tr>

</table>

In practice, one wouldn't bother with that last row, until ''Bb'' is an integer. But observe that if ''N'' had a subroot factor above <math>Aa-Bb=47830.1</math>, Fermat's method would have found it already.

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.

Line 60:

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

<table>

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

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

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

<tr><td>Aa-Bb: </td><td>24582.9</td> <td>24582.2</td> </tr>

</table>

Line 70:

One needn't compute all the square-roots of <math>a^2-N</math>, nor even examine all the values for <math>a</math>. Examine the tableau for <math>N=2345678917</math>:

<table>

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

<tr><td>Bsqb2:</td> <td>76572</td><td>173439</td><td>270308</td><td>367179</td></tr>

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

</table>

One can quickly tell that none of these values of Bsqb2 are squares. Squares end with 0, 1, 4, 5, 9, or 16 [[Modular_arithmetic|modulo]] 20. The values repeat with each increase of <math>a</math> by 10. For this example <math>a^2-N</math> produces 3, 4, 7, 8, 12, and 19 modulo 20 for these values. It is apparent that only the 4 from this list can be a square. Thus, <math>a^2</math> must be 1 mod 20, which means that <math>a</math> is 1 or 9 mod 10; it will produce a Bsqb2 which ends in 4 mod 20, and if Bsqbsq is a square, <math>b</math> will end in 2 or 8 mod 10.

This can be performed with any modulus. Using the same <math>N=2345678917</math>,

Line 92:

Given a sequence of ''a''-values (start, end, and step) and a modulus, one can proceed thus:

:FermatSieve(N, Astartastart, Aendaend, Astepastep, Modulusmodulus)

::Aa &larr; Astartastart

::do Modulusmodulus times:

:::Bsqb2 &larr; Aa*Aa - N

:::if Bsqb2 is a square, modulo Modulusmodulus:

::::FermatSieve(N, Aa, Aendaend, Astepastep * Modulusmodulus, NextModulus)

:::endif

:::Aa &larr; Aa + Astepastep

::enddo

But one stops the recursion, when few ''a''-values remain; that is, when (Aendaend-Astartastart)/Astepastep is small. Also, because ''a'''s step-size is constant, one can compute successive Bsqb2's with additions.

==Multiplier improvement==

Line 108:

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

If one knows the approximate ratio of two factors (<math>d/c</math>), then one can 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 does 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.

Line 115:

==Other improvements==

The fundamental ideas of Fermat's factorization method are the basis of the [[quadratic sieve]] and [[general number field sieve]], the best-known algorithms for factoring "worst-case" large [[semiprimes]]. The primary improvement that quadratic sieve makes over Fermat's factorization method is that instead of simply finding a square in the sequence of ''a''<supmath>a^2 - n</supmath>&minus;''n'', it finds a subset of elements of this sequence whose ''product'' is a square, and it does this in a highly efficient manner. The end result is the same: a difference of square mod ''n'' that, if nontrivial, can be used to factor ''n''.

See also J. McKee, "[http://www.ams.org/mcom/1999-68-228/S0025-5718-99-01133-3/home.html Speeding Fermat's factoring method]", ''Mathematics of Computation'', 68:1729-1737 (1999).