
Glossary: Prime Pages: Top 5000: 
Fermat's method of factoring consists of finding
x and y such that
x^{2}y^{2}=n.
The right side of the equation factors
into (xy)(x+y), and
if xy is not one, then you have
found a nontrivial factorization.
There exists several easy extensions to this idea. For example, instead of solving x^{2}y^{2}=n, we try to find x and y such that x^{2}=y^{2} (mod n). This means n divides x^{2}y^{2}, so if x is not congruent to +y modulo n, then gcd(xy,n) or gcd(x+y,n) must be a nontrivial 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 3^{2}=10^{2} (mod 91), and expect either gcd(103,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 K. Caldwell © 19992017 (all rights reserved)
