Factorización de formas cuadradas de Shanks

La factorización de formas cuadradas de Shanks es un método para factorizar enteros inventado por Daniel Shanks como una mejora del método de factorización de Fermat.

El éxito del método depende de encontrar números enteros ${\displaystyle x}$ e ${\displaystyle y}$ tales que ${\displaystyle x^{2}-y^{2}=N}$, donde ${\displaystyle N}$ es el entero a ser factorizado. Una mejora (indicada por Kraitchik) es buscar enteros ${\displaystyle x}$ e ${\displaystyle y}$ tales que ${\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}$. Encontrando un par adecuado ${\displaystyle (x,y)}$ no se garantiza una factorización de ${\displaystyle N}$, pero esto implica que ${\displaystyle N}$ es un factor de ${\displaystyle x^{2}-y^{2}=(x-y)(x+y)}$, y hay una buena posibilidad de que los divisores primos de ${\displaystyle N}$ estén distribuidos entre esos dos factores, así que el cálculo del máximo común divisor de ${\displaystyle N}$ y ${\displaystyle x-y}$ dará un factor no trivial de ${\displaystyle N}$.

Un algoritmo práctico para encontrar pares ${\displaystyle (x,y)}$ que satisfagan ${\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}$ fue desarrollado por Shanks, que lo llamó Factorización de formas cuadradas (en inglés Square Forms Factorization o SQUFOF). El algoritmo puede ser expresado en términos de fracciones continuas, o en términos de formas cuadráticas. A pesar de que ahora existen métodos de factorización más eficientes disponibles, SQUFOF tiene la ventaja de que es lo suficientemente pequeño para ser implementado en una calculadora programable.

Véase también

• Método de factorización de Fermat

Referencias

• D. A. Buell (1989). Binary Quadratic Forms. Springer-Verlag. ISBN 0-387-97037-1. 
• D. M. Bressoud (1989). Factorisation and Primality Testing. Springer-Verlag. ISBN 0-387-97040-1. 
• Riesel, Hans (1994). Prime numbers and computer methods for factorization (2nd edición). Birkhauser. ISBN 0-8176-3743-5. 

Enlaces externos

• 2005, Stephen S. McMath
• Analysis and Improvement of the Continued Fraction Method of Factorization, Daniel Shanks (transcribed by S.McMath 2004)
• SQUFOF Notes, Daniel Shanks (transcribed by S. McMath 2004)
• Square Form Factorisation, Jason Gower and Samuel Wagstaff