Fermat's factorization method

Fermat's factorization method writes an odd composite number n = p * q as a difference of two squares, n = a^2 - b^2, where a is (p + q) / 2 and b is (p - q) / 2. The method guesses the first square a^2, starting from the square root of n rounded up, and checks whether the remainder b^2 = a^2 - n is also a perfect square. If it is, the factors are a - b and a + b; if not, a is increased by one and the test repeats. The running time grows with the difference between the two factors, so the method can be very fast when the factors are close together, but it becomes extremely slow once they are far apart, and in practice it is rarely used on its own. The cp-algorithms article adds that looking at squares modulo a fixed small number shows that some values of a can be skipped because they cannot produce a square, which is one of several possible optimizations.