Euler's factorization method

Euler's factorization method factors an integer by writing it as a sum of two squares in two different ways. The idea that two distinct representations of an odd positive integer may lead to a factorization was apparently first proposed by Marin Mersenne, but it was not put to use extensively until a hundred years later, by Euler. His most celebrated use of the method was to factor the number 1000009, which had apparently been thought prime. The method is more effective than Fermat's factorization method for integers whose factors are not close together, and potentially much more efficient than trial division when representations as sums of two squares are easy to find. Its great disadvantage is that it cannot be applied to an integer with a prime factor of the form 4k + 3 occurring to an odd power, since such a number can never be a sum of two squares; 3053 = 43 x 71 is one example. That restricted applicability has made it disfavoured for general computer factoring, though James McKee published an attempt in 1996 to turn it into a factoring algorithm for specialised numbers. It rests on the Brahmagupta-Fibonacci identity for products of sums of two squares.