|
Fermat's method of factoring (another Prime Pages' Glossary entries) |
|
|
Glossary:
Prime Pages:
Top 5000:
|
Fermat's method of factoring consists of finding
x and y such that
x2-y2=n.
The right side of the equation factors
into (x-y)(x+y), and
if x-y is not one, then you have
found a non-trivial factorization.
There exists several easy extensions to this idea. For example, instead of solving x2-y2=n, we try to find x and y such that x2=y2 (mod n). This means n divides x2-y2, so if x is not congruent to +y modulo n, then gcd(x-y,n) or gcd(x+y,n) must be a non-trivial factor of n. For example, suppose we wish to factor n=91. The first few squares (modulo 91) are as follows: 1, 4, 9, 16, 25, 36, 49, 64, 81, 9, 30, 53, 78, ...So we see 32=102 (mod 91), and expect either gcd(10-3,91)=7 or gcd(10+3,91)=13 to be a proper divisor of 91. Both are! Fermat's method (and the simple extentions to it above) are not very efficient in finding factors themselves, but are theoretically important in that many more modern methods such as: the quadratic sieve, multiple polynomial quadratic sieve, and the special and the general number field sieves are all based upon this method. Contributed by Lucas Wiman
References:
Chris Caldwell © 1999-2009 (all rights reserved)
|