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úmero Se puede escribir como o como y el método de Euler da la factorización .
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 aparentemente se pensaba anteriormente que era primo aunque no es un pseudoprime según ninguna prueba de primordialidad importante.
El método de factorización de Euler es más efectivo que el de Fermat para 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 [ cita requerida ] . 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 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 nuevamente no se pueden factorizar con 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. Es sólo relativamente recientemente que ha habido intentos de desarrollar el método de Euler en algoritmos de computadora para su uso en números especializados donde se sabe que el método de Euler se puede aplicar.
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 encontramos como producto de sumas de dos cuadrados.
Primero deduce eso
y factorizar ambos lados para obtener
- (1)
Ahora deja y para que existan algunas constantes satisfactorio
- ,
- ,
- ,
- ,
Sustituyendo estos en la ecuación (1) se obtiene
Cancelar los rendimientos de factores comunes
Ahora usando el hecho de que y son pares de números primos relativos, encontramos que
Entonces
Ahora vemos que y
Aplicando la identidad Brahmagupta-Fibonacci obtenemos
Como cada factor es una suma de dos cuadrados, uno de estos debe contener ambos números pares: o . Sin pérdida de generalidad, suponga que el parincluso. La factorización se convierte entonces en
Ejemplo resuelto
Desde:
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 |
Por lo tanto,
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 .