Euler
Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in m ...
'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
A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy.
Some sources use the term pseudoprime t ...
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. Euler's development ultimately permitted much more efficient factoring of numbers and, by the 1910s, the development of large factor tables 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
Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares:
:N = a^2 - b^2.
That difference is algebraically factorable as (a+b)(a-b); if neither factor equals one ...
.
Disadvantage and Limitation
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 number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
s 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
A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations (computation) automatically. Modern digital electronic computers can perform generic sets of operations known as programs. These prog ...
factoring
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s, 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.
Theoretical basis
The
Brahmagupta–Fibonacci identity
In algebra, the Brahmagupta–Fibonacci identity expresses the product of two sums of two squares as a sum of two squares in two different ways. Hence the set of all sums of two squares is closed under multiplication. Specifically, the identity sa ...
states that the product of two sums of two squares is a sum of two squares. Euler's method relies on this theorem but it can be viewed as the converse, given
we find
as a product of sums of two squares.
First deduce that
:
and factor both sides to get
:
(1)
Now let
and
so that there exists some constants
satisfying
*
,
*
,
*
,
*
,
Substituting these into equation (1) gives
:
Canceling common factors yields
:
Now using the fact that
and
are pairs of relatively prime numbers, we find that
*
*
So
*
*
*
*
We now see that
and
Applying the
Brahmagupta–Fibonacci identity
In algebra, the Brahmagupta–Fibonacci identity expresses the product of two sums of two squares as a sum of two squares in two different ways. Hence the set of all sums of two squares is closed under multiplication. Specifically, the identity sa ...
we get
:
As each factor is a sum of two squares, one of these must contain both even numbers: either
or
. Without loss of generality, assume that pair
is even. The factorization then becomes
:
Worked example
Since:
we have from the formula above:
Thus,
:
::
::
::
Pseudocode
function Euler_factorize(int n) -> list
nt if is_prime(n) then
print("Number is not factorable")
exit function
for-loop from a=1 to a=ceiling(sqrt(n))
b2 = n - a*a
b = floor(sqrt(b2))
if b*bb2
break loop preserving a,b
if a*a+b*b!=n then
print("Failed to find any expression for n as sum of squares")
exit function
for-loop from c=a+1 to c=ceiling(sqrt(n))
d2 = n - c*c
d = floor(sqrt(d2))
if d*dd2 then
break loop preserving c,d
if c*c+d*d!=n then
print("Failed to find a second expression for n as sum of squares")
exit function
A = c-a, B = c+a
C = b-d, D = b+d
k = GCD(A,C)//2, h = GCD(B,D)//2
l = GCD(A,D)//2, m = GCD(B,C)//2
factor1 = k*k + h*h
factor2 = l*l + m*m
return list
factor1, factor2
References
*
*
{{number theoretic algorithms
Euler's factorization method