Método de factorización de Euler - Euler's factorization method

El método de factorización de Euler es una técnica para factorizar un número escribiéndolo como una 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 conducir a una factorización fue aparentemente propuesta por primera vez por Marin Mersenne . Sin embargo, Euler no lo utilizó ampliamente hasta cien años después. Su uso más célebre del método que ahora lleva su nombre fue factorizar el número , que al parecer anteriormente se pensaba que era primo, aunque no es un pseudoprime según ninguna prueba importante de primalidad. ${\ displaystyle 1000009}$

El método de factorización de Euler es más efectivo que el de Fermat para los números enteros cuyos factores no están juntos y potencialmente mucho más eficiente que la división de prueba si se pueden encontrar representaciones de números como sumas de dos cuadrados con razonable facilidad. El desarrollo de Euler finalmente permitió una factorización de números mucho más eficiente y, en la década de 1910, el desarrollo de tablas de factores grandes que llegaban a unos diez millones. 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 .

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 ocurriendo con una potencia impar en su factorización prima, ya que tal número nunca puede ser la suma de dos cuadrados. . Los números compuestos pares de la forma 4 k  + 1 son a menudo el producto de dos números primos de la forma 4 k  + 3 (por ejemplo, 3053 = 43 × 71) y, de nuevo, no se pueden factorizar mediante el método de Euler.

Esta aplicabilidad restringida ha hecho que el método de factorización de Euler sea desfavorecido para los algoritmos de factorización por computadora , ya que es poco probable que cualquier usuario que intente factorizar un entero aleatorio sepa si el método de Euler se puede aplicar realmente al entero en cuestión. Sólo 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 donde se sabe que el método de Euler puede aplicarse.

Bases teóricas

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 verse 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 deduce eso

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

y factorizar ambos lados para obtener

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

Ahora vamos y para que existan algunas constantes que satisfagan ${\ Displaystyle k = \ operatorname {gcd} (ac, db)}$${\ Displaystyle h = \ operatorname {gcd} (a + c, d + b)}$${\ Displaystyle l, m, l ', m'}$

• ${\ 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}$

Sustituyendo estos en la ecuación (1) se obtiene

${\ displaystyle klhm '= kmhl'}$

Cancelar los rendimientos de factores comunes

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

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

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

Entonces

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

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

Aplicando la identidad 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 estos debe contener ambos números pares: o . Sin perder la generalidad, suponga 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} \ derecha) \ izquierda (l ^ {2} + m ^ {2} \ derecha). \,}$

Ejemplo resuelto

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

tenemos de la fórmula anterior:

a = 1000	(A) a - c = 28	k = mcd [A, C] = 4
b = 3	(B) a + c = 1972	h = mcd [B, D] = 34
c = 972	(C) d - b = 232	l = mcd [A, D] = 14
d = 235	(D) d + b = 238	m = mcd [B, C] = 116

Así,

${\ displaystyle 1000009 = \ left [\ left ({\ frac {4} {2}} \ right) ^ {2} + \ left ({\ frac {34} {2}} \ right) ^ {2} \ derecha] \ 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 \,}$

Referencias

• Ore, Oystein (1988). "Método de factorización de Euler". Teoría de números y su historia . págs.  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 London Mathematical Society . 4 (28): 351–355. doi : 10.1112 / blms / 28.4.351 .