Euler's factorization method

Euler's factorization method is a method of factorization based upon representing a positive integer $N$ as the sum of two squares in "two different ways":

$N\; =\; a^2+\; b^2\; =\; c^2+\; d^2$ $(1)$

Although the algebraic factorization of binomial numbers cannot factor sums of two squares (indeed a number expressive in "one" way as the sum of two squares is a prime) if one can find two "distinct" representations of a number as sums of two squares it leads as follows to a factorization:

From $N\; =\; a^2\; +\; b^2\; =\; c^2\; +\; d^2$ $(2)$

we get by subtracting $c^2$ and $b^2$ from both sides to create a difference of two squares:$a^2\; -\; c^2\; =\; d^2\; -\; b^2$ $(3)$

and then it follows that:

$(a\; -\; c)cdot(a\; +\; c)\; =\; (d\; -\; b)cdot(d\; +\; b)$ $(4)$

By convention, $d$ and $b$ are either both odd or both even, so that their difference will be even. Now we define a constant $k$ as the greatest common factor of $(a\; -\; c)$ and $(d\; -\; b)$ so that:

$(a\; -\; c)\; =\; kl$ and $(d\; -\; b)\; =\; km$ $GCD\; (l,\; m)\; =\; 1$ so that, after substituting into $(4)$:

$lcdot(a\; +\; c)\; =\; mcdot(d\; +\; b)$ $(5)$

Because $l$ and $m$ are relatively prime, we must have $(a\; +\; c)$ divisible by $m$, which thus gives:

$(a\; +\; c)\; =\; mn$ $(6)$ and;$(d\; +\; b)\; =\; ln$ $(7)$

The resultant factorization of the original number $N$ can be shown to be equal to:

$N\; =\; [(frac\{k\}\{2\})^2\; +\; (frac\{n\}\{2\})^2]\; cdot(m^2\; +\; l^2)$

History and applications

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 Euler one hundred years later. His most celebrated use of the method that now bears his name was to factor the number $N\; =\; 1000009$, which apparently was previously thought to be prime even though it is not a pseudoprime by any major primality test.

Since:

$1000009\; =\; 1000^2\; +\; 3^2\; =\; 972^2\; +\; 235\; ^2$

we have from the formulae above:

Thus,

1000009 $=\; [(frac\{4\}\{2\})^2\; +\; (frac\{34\}\{2\})^2]\; cdot(58^2\; +\; 7^2)$
* $=\; (2^2\; +\; 17^2)cdot(58^2\; +\; 7^2)$
* $=\; (4\; +\; 289)cdot(3364\; +\; 49)$
* $=\; 293cdot3413$

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. Euler's development ultimately permitted much more efficient factoring of numbers and, by the 1910s, the development of large factor table going up to about ten million. 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.

The great disadvantage of Euler's factorization method is that it cannot be applied to factoring an integer with any prime factor of the form 4"k"+3 occurring to an odd power in its prime factorization, as such a number can never be the sum of two squares. Even odd composite numbers of the form 4"k"+1 are often the product of two primes of the form 4"k"+3 (e.g. 3053 = 43 × 71) and again cannot be factored by Euler's method.

This restricted applicability has made Euler's factorization method disfavoured for computer factoring algorithms, since any user attempting to factor a random integer is unlikely to know whether Euler's method can actually be applied to the integer in question. It is only relatively recently that there have been attempts to develop Euler's method into computer algorithms for use on specialised numbers where it is known Euler's method can be applied.

References

* "Euler's Factorization Method"; in Ore, Oystein; "Number Theory and Its History"; pp. 59-64. ISBN 0486656209

* McKee, James; "Turning Euler's Factoring Method into a Factoring Algorithm"; in "Bulletin of the London Mathematical Society" 1996; issue 28 (volume 4); pp. 351-355