Euler's factorization method is a technique for factoring a number by writing it as a sum of two squares in two different ways. For example the number can be written as or as and Euler's method gives the factorization .
The idea that two distinct representations of an odd positive integer may lead to a factorization was apparently first proposed by Marin Mersenne. However, it was not put to use extensively until one hundred years later by Euler. His most celebrated use of the method that now bears his name was to factor the number , which apparently was previously thought to be prime even though it is not a pseudoprime by any major primality test.
Euler's factorization method is more effective than Fermat's for integers whose factors are not close together and potentially much more efficient than trial division if one can find representations of numbers as sums of two squares reasonably easily. The methods used to find representations of numbers as sums of two squares are essentially the same as with finding differences of squares in Fermat's factorization method.