Fermat's factorization method

Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares: That difference is algebraically factorable as ; if neither factor equals one, it is a proper factorization of N. Each odd number has such a representation. Indeed, if is a factorization of N, then Since N is odd, then c and d are also odd, so those halves are integers. (A multiple of four is also a difference of squares: let c and d be even.) In its simplest form, Fermat's method might be even slower than trial division (worst case). Nonetheless, the combination of trial division and Fermat's is more effective than either. One tries various values of a, hoping that , a square. FermatFactor(N): // N should be odd a ← b2 ← aa - N repeat until b2 is a square: a ← a + 1 b2 ← aa - N // equivalently: // b2 ← b2 + 2*a + 1 // a ← a + 1 return a - // or a + For example, to factor , the first try for a is the square root of 5959 rounded up to the next integer, which is 78. Then, . Since 125 is not a square, a second try is made by increasing the value of a by 1. The second attempt also fails, because 282 is again not a square. The third try produces the perfect square of 441. So, , , and the factors of 5959 are and . Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of a and b. That is, is the smallest factor ≥ the square-root of N, and so is the largest factor ≤ root-N. If the procedure finds , that shows that N is prime. For , let c be the largest subroot factor. , so the number of steps is approximately . If N is prime (so that ), one needs steps. This is a bad way to prove primality. But if N has a factor close to its square root, the method works quickly. More precisely, if c differs less than from , the method requires only one step; this is independent of the size of N. Consider trying to factor the prime number N = 2345678917, but also compute b and a − b throughout.