Fermat's method of factoring
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 extensions 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:
- Burton97 (section 5.2)
- D. M. Burton, Elementary number theory, Third edition, McGraw-Hill, 1997. [Burton's texts are excellent introductions to elementary number theory and its history.]