Euler's factorization method

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 ${\displaystyle 1000009}$ can be written as ${\displaystyle 1000^{2}+3^{2}}$ or as ${\displaystyle 972^{2}+235^{2}}$ and Euler's method gives the factorization ${\displaystyle 1000009=293\cdot 3413}$.

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 ${\displaystyle 1000009}$, 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.

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 4k + 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 4k + 1 are often the product of two primes of the form 4k + 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.

The Brahmagupta–Fibonacci identity 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 ${\displaystyle n=a^{2}+b^{2}=c^{2}+d^{2}}$ we find ${\displaystyle n}$ as a product of sums of two squares.

First deduce that

${\displaystyle a^{2}-c^{2}=d^{2}-b^{2}}$

and factor both sides to get

${\displaystyle (ac)(a+c)=(db)(d+b)}$ (1)

Now let ${\displaystyle k=\operatorname {gcd} (ac,db)}$ and ${\displaystyle h=\operatorname {gcd} (a+c,d+b)}$ so that there exists some constants ${\displaystyle l,m,l',m'}$ satisfying

• ${\displaystyle (ac)=kl}$,
• ${\displaystyle (db)=km}$,

${\displaystyle \operatorname {gcd} (l,m)=1}$

• ${\displaystyle (a+c)=hm'}$,
• ${\displaystyle (d+b)=hl'}$,

${\displaystyle \operatorname {gcd} (l',m')=1}$

Substituting these into equation (1) gives

${\displaystyle klhm'=kmhl'}$

Canceling common factors yields

${\displaystyle lm'=l'm}$

Now using the fact that ${\displaystyle (l,m)}$ and ${\displaystyle \left(l',m'\right)}$son pares de números primos relativos, encontramos que

• ${\displaystyle l=l'}$
• ${\displaystyle m=m'}$

Entonces

• ${\displaystyle (ac)=kl}$
• ${\displaystyle (db)=km}$
• ${\displaystyle (a+c)=hm}$
• ${\displaystyle (d+b)=hl}$

Ahora vemos que${\displaystyle m=\operatorname {gcd} (a+c,db)}$y${\displaystyle l=\operatorname {gcd} (ac,d+b)}$

Aplicando la identidad de Brahmagupta-Fibonacci obtenemos

${\displaystyle \left(k^{2}+h^{2}\right)\left(l^{2}+m^{2}\right)=(kl+hm)^{2}+(km-hl)^{2}={\bigl (}(ac)+(a+c){\bigr )}^{2}+{\bigl (}(db)-(d+b){\bigr )}^{2}=(2a)^{2}+(2b)^{2}=4n.}$

Como cada factor es una suma de dos cuadrados, uno de ellos debe contener ambos números pares:${\displaystyle (k,h)}$o${\displaystyle (l,m)}$Sin pérdida de generalidad, supongamos que el par${\displaystyle (k,h)}$es par. La factorización entonces se convierte en

${\displaystyle n=\left(\left({\tfrac {k}{2}}\right)^{2}+\left({\tfrac {h}{2}}\right)^{2}\right)\left(l^{2}+m^{2}\right).\,}$

Desde:${\displaystyle \ 1000009=1000^{2}+3^{2}=972^{2}+235^{2}}$

Tenemos de la fórmula anterior:

De este modo,

${\displaystyle 1000009=\left[\left({\frac {4}{2}}\right)^{2}+\left({\frac {34}{2}}\right)^{2}\right]\cdot \left[\left({\frac {14}{2}}\right)^{2}+\left({\frac {116}{2}}\right)^{2}\right]\,}$

${\displaystyle =\left(2^{2}+17^{2}\right)\cdot \left(7^{2}+58^{2}\right)\,}$

${\displaystyle =(4+289)\cdot (49+3364)\,}$

${\displaystyle =293\cdot 3413\,}$

función Euler_factorize(int n) -> lista[int] si es_primo(n) entonces print("El número no es factorizable") función de salida bucle for desde a=1 hasta a=techo(sqrt(n)) b2 = n - a*a b = piso(raíz cuadrada(b2)) si b*b==b2 romper bucle preservando a,b si a*a+b*b!=n entonces print("No se encontró ninguna expresión para n como suma de cuadrados") función de salida bucle for desde c=a+1 hasta c=techo(sqrt(n)) d2 = n - c*c d = piso(raíz cuadrada(d2)) si d*d==d2 entonces romper bucle preservando c,d si c*c+d*d!=n entonces print("No se pudo encontrar una segunda expresión para n como suma de cuadrados") función de salida A = ca, B = c+a C = bd, D = b+d k = MCD(A,C)//2, h = MCD(B,D)//2 l = MCD(A,D)//2, m = MCD(B,C)//2 factor1 = k*k + h*h factor2 = l*l + m*m devolver lista[ factor1, factor2 ]

• Ore, Oystein (1988). «El método de factorización de Euler» . Teoría de números y su historia . Courier Corporation. págs. 59-64 . ISBN  978-0-486-65620-5.
• McKee, James (1996). "Convirtiendo el método de factorización de Euler en un algoritmo de factorización". Boletín de la Sociedad Matemática de Londres . 4 (28): 351– 355. doi : 10.1112/blms/28.4.351 .