El éxito del método depende de encontrar números enteros e tales que , donde es el entero a ser factorizado. Una mejora (indicada por Kraitchik) es buscar enteros e tales que . Encontrando un par adecuado no se garantiza una factorización de , pero esto implica que es un factor de , y hay una buena posibilidad de que los divisores primos de estén distribuidos entre esos dos factores, así que el cálculo del máximo común divisor de y dará un factor no trivial de .
Un algoritmo práctico para encontrar pares que satisfagan 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.
D. A. Buell (1989). Binary Quadratic Forms. Springer-Verlag. ISBN0-387-97037-1.
D. M. Bressoud (1989). Factorisation and Primality Testing. Springer-Verlag. ISBN0-387-97040-1.
Riesel, Hans (1994). Prime numbers and computer methods for factorization (2nd edición). Birkhauser. ISBN0-8176-3743-5.
Enlaces externos
Square Form Factorisation, Jason Gower and Samuel Wagstaff
Datos:Q4291872
Agosto 18, 2021
factorización, formas, cuadradas, shanks, factorización, formas, cuadradas, shanks, método, para, factorizar, enteros, inventado, daniel, shanks, como, mejora, método, factorización, fermat, éxito, método, depende, encontrar, números, enteros, displaystyle, di. La factorizacion de formas cuadradas de Shanks es un metodo para factorizar enteros inventado por Daniel Shanks como una mejora del metodo de factorizacion de Fermat El exito del metodo depende de encontrar numeros enteros x displaystyle x e y displaystyle y tales que x 2 y 2 N displaystyle x 2 y 2 N donde N displaystyle N es el entero a ser factorizado Una mejora indicada por Kraitchik es buscar enteros x displaystyle x e y displaystyle y tales que x 2 y 2 mod N displaystyle x 2 equiv y 2 pmod N Encontrando un par adecuado x y displaystyle x y no se garantiza una factorizacion de N displaystyle N pero esto implica que N displaystyle N es un factor de x 2 y 2 x y x y displaystyle x 2 y 2 x y x y y hay una buena posibilidad de que los divisores primos de N displaystyle N esten distribuidos entre esos dos factores asi que el calculo del maximo comun divisor de N displaystyle N y x y displaystyle x y dara un factor no trivial de N displaystyle N Un algoritmo practico para encontrar pares x y displaystyle x y que satisfagan x 2 y 2 mod N displaystyle x 2 equiv y 2 pmod N fue desarrollado por Shanks que lo llamo Factorizacion de formas cuadradas en ingles Square Forms Factorization o SQUFOF El algoritmo puede ser expresado en terminos de fracciones continuas o en terminos de formas cuadraticas A pesar de que ahora existen metodos de factorizacion mas eficientes disponibles SQUFOF tiene la ventaja de que es lo suficientemente pequeno para ser implementado en una calculadora programable Vease tambien EditarMetodo de factorizacion de FermatReferencias EditarD 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 edicion Birkhauser ISBN 0 8176 3743 5 Enlaces externos Editar2005 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 Datos Q4291872Obtenido de https es wikipedia org w index php title Factorizacion de formas cuadradas de Shanks amp oldid 137601520, wikipedia, wiki, leyendo, leer, libro, biblioteca,
