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 formula_2; if neither factor equals one, it is a proper factorization of "N". Each odd number has such a representation. Indeed, if formula_3 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. Basic method. One tries various values of "a", hoping that formula_5, a square. For example, to factor formula_6, the first try for "a" is the square root of rounded up to the next integer, which is . Then, formula_7. 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, formula_8, formula_9, and the factors of are formula_10 and formula_11. Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of "a" and "b". That is, formula_12 is the smallest factor ≥ the square-root of "N", and so formula_13 is the largest factor ≤ root-"N". If the procedure finds formula_14, that shows that "N" is prime. For formula_15, let "c" be the largest subroot factor. formula_16, so the number of steps is approximately formula_17. If "N" is prime (so that formula_18), one needs formula_19 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 formula_20 from formula_21, the method requires only one step; this is independent of the size of "N". Fermat's and trial division. Consider trying to factor the prime number , but also compute "b" and throughout. Going up from formula_22, we can tabulate: In practice, one wouldn't bother with that last row until "b" is an integer. But observe that if "N" had a subroot factor above formula_23, Fermat's method would  have found it already. Trial division would normally try up to 48,432; but after only four Fermat steps, we need only divide up to 47830, to find a factor or prove primality. This all suggests a combined factoring method. Choose some bound formula_24; use Fermat's method for factors between formula_22 and formula_26. This gives a bound for trial division which is formula_27. In the above example, with formula_28 the bound for trial division is 47830. A reasonable choice could be formula_29 giving a bound of 28937. In this regard, Fermat's method gives diminishing returns. One would surely stop  before this point: Sieve improvement. When considering the table for formula_30, one can quickly tell that none of the values of formula_31 are squares: It is not necessary to compute all the square-roots of formula_32, nor even examine all the values for . Squares are always congruent to 0, 1, 4, 5, 9, 16 modulo 20. The values repeat with each increase of by 10. In this example, N is 17 mod 20, so subtracting 17 mod 20 (or adding 3), formula_32 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, formula_34 must be 1 mod 20, which means that is 1, 9, 11 or 19 mod 20; it will produce a formula_31 which ends in 4 mod 20 and, if square, will end in 2 or 8 mod 10. This can be performed with any modulus. Using the same formula_30, One generally chooses a power of a different prime for each modulus. Given a sequence of "a"-values (start, end, and step) and a modulus, one can proceed thus: But the recursion is stopped when few "a"-values remain; that is, when  ()/ is small. Also, because "a"'s step-size is constant, one can compute successive b2's with additions. Multiplier improvement. Fermat's method works best when there is a factor near the square-root of "N". If the approximate ratio of two factors (formula_37) is known, then a rational number formula_38 can be picked near that value. formula_39, and Fermat's method, applied to "Nuv", will find the factors formula_40 and formula_41 quickly. Then formula_42 and formula_43. (Unless "c" divides "u" or "d" divides "v".) Generally, if the ratio is not known, various formula_44 values can be tried, and try  to factor each resulting "Nuv". R. Lehman devised a systematic way to do this, so that Fermat's plus trial division can factor N in formula_45 time. Other improvements. The fundamental ideas of Fermat's factorization method are the basis of the quadratic sieve and general number field sieve, the best-known algorithms for factoring large semiprimes, which are the "worst-case". The primary improvement that quadratic sieve makes over Fermat's factorization method is that instead of simply finding a square in the sequence of formula_46, it finds a subset of elements of this sequence whose "product" is a  square, and it does this in a highly efficient manner. The end result is the same: a difference of square mod "n" that, if nontrivial, can be used to factor "n". Factorization with rectangles. The method can be modified to use rectangles instead of squares, by adding a constant c: formula_47 Factorization with cubes. formula_48 Factorization with cuboids. formula_49