Fermat's factorization method: Difference between revisions

Revision as of 12:13, 21 October 2007

Revision as of 12:15, 21 October 2007

Line 68:

</table>

One can quickly tell that none of these values of Bsq isare squaresquares. 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 performed with any modulus. Using the same <math>N=2345678917</math>,