Fermat's factorization method: Difference between revisions

Revision as of 22:36, 14 May 2006

Revision as of 22:56, 14 May 2006

Line 70:

One can quickly tell that none of these values of Bsq 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 Bsq which ends in 4 mod 20, and if Bsq is a square, <math>b</math> will end in 2 or 8 mod 10.

This can be generalizedperformed towith any modulus. ForUsing thatthe same ''<math>N''=2345678917</math>,

<table>

<tr><td>modulo 16:</td><td>BsqSquares must beare</td> <td>0, 1, 4, or 9</td> </tr>

<tr><td></td> <td>soN Amod must16 beis</td><td>3 5 11 or 13</td></tr>

<tr><td>modulo 9:</td> <td>Bsqso must<math>a^2</math> can only be</td> <td>0 1 4 or 79</td> </tr>

<tr><td></td> <td>soand A<math>a</math> must be</td><td>43 or 5 modulo 8</td> </tr>

<tr><td>etc.modulo 9:</td> <td>Squares are</td> <td>0, 1, 4, or 7</td> </tr>

<tr><td></td> <td>N mod 9 is</td><td>7</td></tr>

<tr><td></td> <td>so <math>a^2</math> can only be</td><td>7</td></tr>

<tr><td></td> <td>and <math>a</math> must be</td><td>4 or 5 modulo 9</td></tr>

</table>

One generally chooses a power of a different prime for each modulus.