Fermat's factorization method: Difference between revisions

Revision as of 18:09, 25 May 2009

Revision as of 22:35, 26 May 2009

Line 13:

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

::Aa ← ceil(sqrt(N))

::Bsqb2 ← Aa*Aa - N

::while Bsqb2 isn't a square:

:::Aa ← Aa + 1

:::Bsqb2 ← Aa*Aa - N // equivalently: Bsqb2 ← Bsqb2 + 2*Aa - 1

::endwhile

::return Aa - sqrt(Bsqb2) // or Aa + sqrt(Bsqb2)

For example, to factor <math>N=5959</math>, one computes

{| class="wikitable"

<table>

! a:

<tr><td>A:</td><td>78</td><td>79</td><td>80</td></tr>

| 78

<tr><td>Bsq:</td><td>125</td><td>282</td><td>441</td></tr>

| 79

</table>

| 80

The third try produces a square. <math>A=80</math>, <math>B=21</math>, and the factors are <math>A-B = 59</math>, and <math>A+B = 101</math>.

|-

! b2:

| 125

| 282

| 441

|}

The third try produces a square. <math>Aa=80</math>, <math>Bb=21</math>, and the factors are <math>Aa-Bb = 59</math>, and <math>Aa+Bb = 101</math>.

Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of ''a'' and ''b''. That is, <math>a+b</math> is the smallest factor &ge; the square-root of ''N''. And so <math>a-b = N/(a+b)</math> is the largest factor &le; root-''N''. If the procedure finds <math>N=1*N</math>, that shows that ''N'' is prime.