Método de factorización de Euler

El método de factorización de Euler es una técnica para factorizar un número escribiéndolo como suma de dos cuadrados de dos formas diferentes. Por ejemplo, el númerose puede escribir comoo comoy el método de Euler da la factorización. ${\displaystyle 1000009}$ ${\displaystyle 1000^{2}+3^{2}}$ ${\displaystyle 972^{2}+235^{2}}$ ${\displaystyle 1000009=293\cdot 3413}$

La idea de que dos representaciones distintas de un entero positivo impar pueden dar lugar a una factorización fue aparentemente propuesta por primera vez por Marin Mersenne . Sin embargo, no se utilizó ampliamente hasta cien años después por Euler. Su uso más célebre del método que ahora lleva su nombre fue factorizar el número , que aparentemente antes se pensaba que era primo aunque no es un pseudoprimo según ninguna prueba de primalidad importante. ${\displaystyle 1000009}$

El método de factorización de Euler es más eficaz que el de Fermat para los números enteros cuyos factores no están muy próximos entre sí y potencialmente mucho más eficiente que la división por tanteo si se pueden encontrar representaciones de números como sumas de dos cuadrados con relativa facilidad. Los métodos utilizados para encontrar representaciones de números como sumas de dos cuadrados son esencialmente los mismos que para encontrar diferencias de cuadrados en el método de factorización de Fermat .

Desventajas y limitaciones

La gran desventaja del método de factorización de Euler es que no se puede aplicar a la factorización de un número entero con cualquier factor primo de la forma 4 k  + 3 que aparezca elevado a una potencia impar en su factorización prima, ya que dicho número nunca puede ser la suma de dos cuadrados. Los números compuestos pares impares de la forma 4 k  + 1 suelen ser el producto de dos primos de la forma 4 k  + 3 (por ejemplo, 3053 = 43 × 71) y, de nuevo, no se pueden factorizar con el método de Euler.

Esta aplicabilidad restringida ha hecho que el método de factorización de Euler no sea el preferido para los algoritmos de factorización informática , ya que cualquier usuario que intente factorizar un entero aleatorio es poco probable que sepa si el método de Euler puede realmente aplicarse al entero en cuestión. Hace relativamente poco tiempo que ha habido intentos de desarrollar el método de Euler en algoritmos informáticos para su uso en números especializados en los que se sabe que el método de Euler puede aplicarse.

Fundamento teórico

La identidad de Brahmagupta-Fibonacci establece que el producto de dos sumas de dos cuadrados es una suma de dos cuadrados. El método de Euler se basa en este teorema, pero puede considerarse como el inverso, dado que encontramos como un producto de sumas de dos cuadrados. ${\displaystyle n=a^{2}+b^{2}=c^{2}+d^{2}}$ ${\displaystyle n}$

Primero deduzcamos que

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

y factoriza ambos lados para obtener

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

Sea ahora y de modo que existan algunas constantes que satisfagan ${\displaystyle k=\operatorname {gcd} (a-c,d-b)}$ ${\displaystyle h=\operatorname {gcd} (a+c,d+b)}$ ${\displaystyle l,m,l',m'}$

• ${\displaystyle (a-c)=kl}$,
• ${\displaystyle (d-b)=km}$,

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

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

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

Sustituyendo estos en la ecuación (1) obtenemos

${\displaystyle klhm'=kmhl'}$

La cancelación de factores comunes da como resultado

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

Ahora, utilizando el hecho de que y son pares de números relativamente primos, encontramos que ${\displaystyle (l,m)}$ ${\displaystyle \left(l',m'\right)}$

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

Entonces

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

Ahora vemos eso y ${\displaystyle m=\operatorname {gcd} (a+c,d-b)}$ ${\displaystyle l=\operatorname {gcd} (a-c,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 (}(a-c)+(a+c){\bigr )}^{2}+{\bigl (}(d-b)-(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: o bien o . Sin pérdida de generalidad, supongamos que el par es par. La factorización se convierte entonces en ${\displaystyle (k,h)}$ ${\displaystyle (l,m)}$ ${\displaystyle (k,h)}$

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

Ejemplo resuelto

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\,}$

Pseudocódigo

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 conservando a,b si a*a+b*b!=n entonces print("No se pudo encontrar 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 conservando 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 ]

Referencias

• Ore, Oystein (1988). "El método de factorización de Euler". Teoría de números y su historia . Courier Corporation. pp. 59–64. ISBN 978-0-486-65620-5.
• McKee, James (1996). "Convertir 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.