Fermat's factorization method: Difference between revisions

Revision as of 08:08, 14 May 2006

Revision as of 22:36, 14 May 2006

Line 61:

==Sieve improvement==

One needn't compute all thosethe square-roots of <math>a^2-N</math>., Looknor againeven atexamine thisall the values for <math>a</math>. Examine the tableau for <math>N=2345678917</math>.:

<table>

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

Line 68:

</table>

One can quickly tell at a glance that thenone first andof thirdthese values of Bsq aren'tare squares. Squares end with 0, 1, 4, 5, 69, or 9.16 Not[[Modular_arithmetic|modulo]] only20. that:The thevalues 11threpeat andwith 13theach valuesincrease aren'tof squares,<math>a</math> eitherby 10. If ''For this example <math>a''^2-N</math> isproduces increased3, by4, 107, Bsq8, will12, endand with19 themodulo same20 digitfor these values. One findsIt is apparent that ''only the 4 from this list can be a'' mustsquare. end inThus, <math>a^2</math> must be 1 4mod 620, which means that <math>a</math> is 1 or 9 mod 10; it will produce a Bsq which ends in 4 mod 20, toand makeif Bsq is a square, <math>b</math> will end in 2 or 8 mod 10.

This can be generalized to any modulus. For that same ''N'',