Factorización de formas cuadradas de Shanks

La factorización de formas cuadradas de Shanks es un método de factorización de números enteros ideado por Daniel Shanks como una mejora del método de factorización de Fermat .

El éxito del método de Fermat depende de encontrar números enteros y tales que , donde es el número entero que se va a factorizar. Una mejora (observada por Kraitchik ) es buscar números enteros y tales que . Encontrar un par adecuado no garantiza una factorización de , pero implica que es un factor de , y hay una buena probabilidad de que los divisores primos de se distribuyan entre estos dos factores, de modo que el cálculo del máximo común divisor de y dará un factor no trivial de . ${\estilo de visualización x}$${\estilo de visualización y}$${\displaystyle x^{2}-y^{2}=N}$${\estilo de visualización N}$${\estilo de visualización x}$${\estilo de visualización y}$${\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}$${\estilo de visualización (x,y)}$${\estilo de visualización N}$${\estilo de visualización N}$${\displaystyle x^{2}-y^{2}=(xy)(x+y)}$${\estilo de visualización N}$${\estilo de visualización N}$${\estilo de visualización xy}$${\estilo de visualización N}$

Shanks desarrolló un algoritmo práctico para encontrar pares que satisfagan las necesidades , al que denominó Factorización de Formas Cuadradas o SQUFOF. El algoritmo se puede expresar en términos de fracciones continuas o en términos de formas cuadráticas. Aunque ahora hay métodos de factorización mucho más eficientes disponibles, SQUFOF tiene la ventaja de que es lo suficientemente pequeño como para implementarse en una calculadora programable. Shanks lo programó en una HP-65 , fabricada en 1974, que tiene almacenamiento para números de solo nueve dígitos y permite solo 100 pasos/pulsaciones de teclas de programación. Hay versiones del algoritmo que utilizan poca memoria y versiones que almacenan una lista de valores que se ejecutan más rápidamente. ${\estilo de visualización (x,y)}$${\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}$

En 1858, el matemático checo Václav Šimerka utilizó un método similar a SQUFOF para factorizar . ^[1]${\estilo de visualización (10^{17}-1)/9}$ ${\estilo de visualización =}$ ${\displaystyle 11111111111111111}$ ${\estilo de visualización =}$ ${\estilo de visualización 2071723\cdot 5363222357}$

Nota: Esta versión del algoritmo funciona en algunos ejemplos, pero a menudo queda atrapada en un bucle.

Esta versión no utiliza una lista.

Entrada : , el número entero a factorizar, que no debe ser ni un número primo ni un cuadrado perfecto , y un entero positivo pequeño, . ${\estilo de visualización N}$${\estilo de visualización k}$

Salida : un factor no trivial de . ${\estilo de visualización N}$

El algoritmo:

Inicializar${\displaystyle i=0,P_{0}=\lfloor {\sqrt {kN}}\rfloor ,Q_{-1}=1,Q_{0}=kN-P_{0}^{2}.}$

Repetir

${\displaystyle i=i+1,b_{i}=\left\lfloor {\frac {P_{0}+P_{i-1}}{Q_{i-1}}}\right\rfloor ,P_{i}=b_{i}Q_{i-1}-P_{i-1},Q_{i}=Q_{i-2}+b_{i}(P_{i-1}-P_{i})}$

hasta es un cuadrado perfecto con un valor impar de . ${\displaystyle Q_{i}}$${\estilo de visualización i}$

Iniciar la segunda fase (ciclo inverso).

Inicialice , , y , donde , y son de la fase anterior. El utilizado en el cálculo de es el valor calculado recientemente de . ${\displaystyle b_{0}=\left\lfloor {\frac {P_{0}-P_{i}}{\sqrt {Q_{i}}}}\right\rfloor }$${\displaystyle Q_{-1}={\sqrt {Q_{i}}}}$${\displaystyle P_{0}=b_{0}{\sqrt {Q_{i}}}+P_{i}}$$Estilo de visualización P_{0}, P_{i}}$${\displaystyle Q_{i}}$$Estilo de visualización b_{0}$${\estilo de visualización P_{0}}$$Estilo de visualización b_{0}$

Establezca y , donde es el valor recientemente calculado de . ${\displaystyle i=0}$${\displaystyle Q_{0}={\frac {kN-P_{0}^{2}}{Q_{-1}}}}$${\estilo de visualización P_{0}}$${\estilo de visualización P_{0}}$

Repetir

${\displaystyle i=i+1,b_{i}=\left\lfloor {\frac {P_{0}+P_{i-1}}{Q_{i-1}}}\right\rfloor ,P_{i}=b_{i}Q_{i-1}-P_{i-1},Q_{i}=Q_{i-2}+b_{i}(P_{i-1}-P_{i})}$

hasta ^{[ cita requerida ]}${\displaystyle P_{i}=P_{i-1}.}$

Entonces, si no es igual a y no es igual a , entonces es un factor no trivial de . De lo contrario, pruebe con otro valor de . ^{[ cita requerida ]}${\displaystyle f=\mcd(N,P_{i})}$${\estilo de visualización 1}$${\estilo de visualización N}$${\estilo de visualización f}$${\estilo de visualización N}$${\estilo de visualización k}$

El método de Shanks tiene complejidad temporal . ^[2]${\displaystyle O({\sqrt[{4}]{N}})}$

Stephen S. McMath escribió una discusión más detallada de las matemáticas del método de Shanks, junto con una prueba de su corrección. ^[3]

Dejar${\estilo de visualización N=11111}$

${\displaystyle Q_{-1}=1}$

Aquí tenemos un cuadrado perfecto, por lo que termina la primera fase. ${\displaystyle Q_{5}=25}$

Para la segunda fase, establezca . Luego: ${\displaystyle Q_{-1}={\sqrt {25}}=5}$

Aquí termina la segunda fase. Ahora calcula , que es un factor de . $Estilo de visualización P_{3}=P_{4}=82$${\displaystyle mcd(11111,82)=41}$${\estilo de visualización 11111}$

De este modo, . ${\displaystyle N=11111=41\cdot 271}$

A continuación se muestra un ejemplo de una función C para realizar la factorización SQUFOF en números enteros sin signo no mayores a 64 bits, sin desbordamiento de las operaciones transitorias. ^{[ cita requerida ]}

#include <inttypes.h> #define nelems(x) (tamaño de(x) / tamaño de((x)[0])) 


const int multiplicador [] = { 1 , 3 , 5 , 7 , 11 , 3 * 5 , 3 * 7 , 3 * 11 , 5 * 7 , 5 * 11 , 7 * 11 , 3 * 5 * 7 , 3 * 5 * 11 , 3 * 7 * 11 , 5 * 7 * 11 , 3 * 5 * 7 * 11 };                   

uint64_t SQUFOF ( uint64_t N ) { uint64_t D , Po , P , Pprev , Q , Qprev , q , b , r , s ; uint32_t L , B , i ; s = ( uint64_t )( sqrtl ( N ) + 0.5 ); si ( s * s == N ) devuelve s ; para ( int k = 0 ; k < nelems ( multiplicador ) && N <= UINT64_MAX / multiplicador [ k ]; k ++ ) { D = multiplicador [ k ] * N ; Po = Pprev = P = sqrtl ( D ); Qprev = 1 ; Q = D - Po * Po ; L = 2 * sqrtl ( 2 * s ); B = 3 * L ; para ( i = 2 ; i < B ; i ++ ) { b = ( uint64_t )(( Po + P ) / Q ); P = b * Q - P ; q = Q ; Q = Qprev + b * ( Pprev - P ); r = ( uint64_t )( sqrtl ( Q ) + 0.5 ); si ( ! ( i & 1 ) &&    

              
       
      
         
                 
          
              
          
            
              
            
                  
                
                
              
                  
              
                 r * r == Q ) break ; Qprev = q ; Pprev = P ; }; if ( i >= B ) continue ; b = ( uint64_t )(( Po - P ) / r ); Pprev = P = b * r + P ; Qprev = r ; Q = ( D - Pprev * Pprev ) / Qprev ; i = 0 ; do { b = ( uint64_t )(( Po + P ) / Q ); Pprev = P ; P = b * Q - P ; q = Q ; Q = Qprev + b * ( Pprev - P ); Qprev = q ; i ++ ; } while ( P != Pprev ) ; r = mcd ( N , Qprev ); if ( r != 1 && r != N ) return r ; } return 0 ; }   
              
              
        
            
            
              
          
            
          
         
                
              
                
              
                  
              
            
            
           
                 
    
     

• DA Buell (1989). Formas cuadráticas binarias . Springer-Verlag. ISBN 0-387-97037-1.
• DM Bressoud (1989). Factorización y pruebas de primalidad . Springer-Verlag. ISBN 0-387-97040-1.
• Riesel, Hans (1994). Números primos y métodos informáticos para la factorización (2.ª ed.). Birkhauser. ISBN 0-8176-3743-5.
• Samuel S. Wagstaff, Jr. (2013). El placer de factorizar. Providence, RI: American Mathematical Society. págs. 163–168. ISBN 978-1-4704-1048-3.

• Daniel Shanks: Análisis y mejora del método de factorización de fracciones continuas (transcrito por S. McMath, 2004)
• Daniel Shanks: Notas sobre SQUFOF (transcripción de S. McMath, 2004)
• Stephen S. McMath: Factorización de números enteros en paralelo utilizando formas cuadráticas, 2005
• S. McMath, F. Crabbe, D. Joyner: Fracciones continuas y SQUFOF paralelas, 2005
• Jason Gower, Samuel Wagstaff: Factorización de forma cuadrada (publicado)
• Algoritmo de factorización SQUFOF de Shanks
• biblioteca-matemática-java