Método de factorización de Euler

El método de factorización de Euler es un método de factorización basado en la representación de un entero positivo N como la suma de dos cuadrados de dos maneras distintas:

N = a² + b² = c² + d²

Aunque la factorización algebraica de números binomiales no sirve para factorizar sumas de dos cuadrados (en efecto un número que se puede expresar de una forma como suma de dos cuadrados es un número primo) si se pueden hallar dos representaciones distintas de un número como suma de dos cuadrados se sigue de ahí una factorización:

Partiendo de N = a² + b² = c² + d²

se resta b² + c² a ambos lados de la igualdad para crear una diferencia de dos cuadrados:

a² − c² = d² − b²

y de ahí se sigue que:

Supóngase sin pérdida de generalidad que d y b son ambos pares o bien ambos impares, de forma que su diferencia es par. Ahora se define una constante k igual al máximo común divisor de (a − c) y (d − b) de forma que:

(a − c) = kl y (d − b) = km, con mcd(l,m) = 1

de forma que, tras sustituir en la expresión anterior:

Como l y m son primos entre sí, se sigue que (a + c) es divisible por m, lo que nos da:

(a + c) = mn y;

(d + b) = ln

La factorización del número original n se puede mostrar que es igual a:

Historia y aplicaciones

La idea de que dos representaciones distintas de un entero positivo diera lugar a una factorización fue aparentemente planteada por primera vez por Marin Mersenne. Sin embargo, no fue hasta Euler, cien años después, que su uso empezara a extenderse. Su más celebrado uso del método que hoy lleva su nombre fue el de factorizar el número N = 1000009, que, al parecer, se pensaba que era primo a pesar de que ninguno de los principales tests de primalidad lo da como pseudoprimo.

Como:

1000009 = 1000² + 3² = 972² + 235²

se tiene por las fórmulas anteriores:

Así,

1000009

El método de factorización de Euler es más efectivo que el de Fermat para números naturales cuyos factores no sean próximos entre sí y es potencialmente mucho más eficiente que la división por tentativa si se pueden hallar representaciones de números como suma de cuadrados de forma razonablemente fácil. El desarrollo de Euler permitió una factorización mucho más eficiente, y, para los años 1910, el desarrollo de una tabla de factores de números hasta 10 millones. Los métodos empleados para encontrar representaciones de números como sumas de dos cuadrados son esencialmente los mismos que se usan para encontrar las diferencias de cuadrados en el método de Fermat.

Desventaja

La gran desventaja del método de factorización de Euler es que no se puede emplear para factorizar un número que tenga algún factor primo de la forma 4k+3 elevado a una potencia impar en su factorización como producto de primos, ya que tal número no podría ser la suma de dos cuadrados. Incluso algunos números compuestos impares de la forma 4k+1 son el producto de dos primos de la forma 4k+3 (por ejemplo, 3053 = 43 × 71) y por ello no admiten factorización a través del método de Euler.

Esta restricción en su uso ha restado protagonismo al método de Euler en el campo de los algoritmos informáticos de factorización, ya que un usuario que intente factorizar un número aleatorio no tiene por qué saber (y en general no sabe) si el método de Euler se puede aplicar a ese número. Sólo recientemente se ha intentado desarrollar el método de Euler en forma de algoritmos informáticos para emplearse en números especiales en los que se sepa que se puede aplicar el método de Euler.

Referencias

• "Euler's Factorization Method"; in Ore, Oystein; Number Theory and Its History; pp. 59-64. ISBN 0-486-65620-9
• McKee, James; "Turning Euler's Factoring Method into a Factoring Algorithm"; in Bulletin of the London Mathematical Society 1996; entrega 28 (volumen 4); pp. 351-355