Shanks kvadrat bildar faktorisering

Shanks fyrkantsformfaktorisering är en metod för heltalsfaktorisering utarbetad av Daniel Shanks som en förbättring av Fermats faktoriseringsmetod .

Framgången för Fermats metod beror på att hitta heltal $x$ och $y$ så att $x^{2}-y^{2}=N$ , där $N$ är det heltal som ska faktoriseras. En förbättring (märkt av Kraitchik ) är att leta efter heltal $x$ och $y$ så att $x^{2}\equiv y^{2 }{\pmod {N}}$ . Att hitta ett lämpligt par $(x,y)$ garanterar inte en faktorisering av $N$ , men det innebär att $N$ är en faktor på ${\displaystyle x^{2}-y^{2}=(xy)(x+y)} ,$ och det finns en god chans att primtalsdivisorerna för N $\ displaystyle N}$ är fördelade mellan dessa två faktorer, så att beräkning av den största gemensamma divisorn för $N$ och $xy$ ger en icke-trivial faktor på $N$ .

En praktisk algoritm för att hitta par $(x,y)$ som uppfyller $x^{2}\equiv y^{2}{\pmod { N}}$ utvecklades av Shanks, som kallade det Square Forms Factorization eller SQUFOF. Algoritmen kan uttryckas i termer av fortsatta bråk eller i termer av kvadratiska former. Även om det nu finns mycket effektivare faktoriseringsmetoder tillgängliga, har SQUFOF fördelen att den är tillräckligt liten för att kunna implementeras på en programmerbar kalkylator.

År 1858 använde den tjeckiske matematikern Václav Šimerka en metod liknande SQUFOF to factor $(10^{17}-1)/9$$=$$\1111111111style11111111111111111111111111111111111 }$$=$$2071723\cdot 5363222357$ .

Algoritm

Inmatning : $N$ , det heltal som ska faktoriseras, vilket varken får vara ett primtal eller en perfekt kvadrat , och en liten multiplikator $k$ .

Output : en icke-trivial faktor av $N$ .

Algoritmen:

Initiera $P_{0}=\lgolv {\sqrt {kN}}\rgolv ,Q_{0}=1,Q_{1}=kN-P_{0}^{2}.$

Upprepa

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

tills $Q_{i+1}$ är en perfekt kvadrat vid vissa jämna $i+1$ .

Initiera $b_{0}=\ vänster\lgolv {\frac {P_{0}-P_{i}}{\sqrt {Q_{i+1}}}}\höger\rgolv ,P_{0}=b_{0}{\sqrt {Q_{ i+1}}}+P_{i},Q_{0}={\sqrt {Q_{i+1}}},Q_{1}={\frac {kN-P_{0}^{2}} {Q_{0}}}$

Upprepa

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

tills $P_{i}=P_{i-1}.$

Sedan om $f=\gcd(N,P_{i})$ inte är lika med $1$ och inte lika med $N$ , då $f$ är en icke-trivial faktor av $N$ . Försök annars med ett annat värde på $k$ .

Shanks metod har tidskomplexitet $O({\sqrt[{4}]{N}})$ .

Stephen S. McMath skrev en mer detaljerad diskussion om matematiken i Shanks metod, tillsammans med ett bevis på dess riktighet.

Exempel

Låt $N=11111,k=1$

Cykla framåt
$i$	$P_{i}$	$Q_{i}$	$b_{i}$
$0$	$105$	$1$
$1$	$67$	$86$	$2$
$2$	$87$	$77$	$2$
$3$	$97$	$46$	$4$
$4$	$88$	$37$	$5$
$5$	$94$	$91$	$2$
$6$		$25$

Här är $Q_{6}=25$ en perfekt kvadrat.

Omvänd cykel
$i$	$P_{i}$	$Q_{i}$	$b_{i}$
$0$	$104$	$5$	$2$
$1$	$73$	$59$	$3$
$2$	$25$	$98$	$1$
$3$	$82$	$107$	$1$
$4$	$82$	$41$	$4$

Här $P_{3}=P_{4}=82$ .

$gcd(11111,82)=41$ , vilket är en faktor på $11111$ .

Således är $N=11111=41\cdot 271$

Exempel på implementeringar

Nedan är ett exempel på C-funktion för att utföra SQUFOF-faktorisering på heltal utan tecken som inte är större än 64 bitar, utan översvämning av transientoperationerna.

 


                   

    

              
       
      
         
        0         
          
              
          
            
              
            
                  
                
                
              
                  
              
                    
              
              
        
            
            
              
          
            
          0
         
                
              
                
              
                  
              
            
            
           
                 
    
     0
 #include  <inttypes.h>  #define nelems(x) (sizeof(x) / sizeof((x)[0]))  const  int  multiplikator  []  =  {  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  );  if  (  s  *  s  ==  N  )  returnera  s  ;  för  (  int  k  =  ;  k  <  nelems  (  multiplikator  )  &&  N  <=  UINT64_MAX  /  multiplikator  [  k  ];  k  ++  )  {  D  =  multiplikator  [  k  ]  *  N  ;  Po  =  Pprev  =  P  =  sqrtl  (  D  );  Qprev  =  1  ;  Q  =  D  -  Po  *  Po  ;  L  =  2  *  sqrtl  (  2  *  s  );  B  =  3  *  L  ;  för  (  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  );  om  (  !  (  i  &  1  )  &&  r  *  r  ==  Q  )  break  ;  Qprev  =  q  ;  Pprev  =  P  ;  };  if  (  i  >=  B  )  fortsätt  ;  b  =  (  uint64_t  )((  Po  -  P  )  /  r  );  Pprev  =  P  =  b  *  r  +  P  ;  Qprev  =  r  ;  Q  =  (  D  -  Pprev  *  Pprev  )  /  Qprev  ;  i  =  ;  gör  {  b  =  (  uint64_t  )((  Po  +  P  )  /  Q  );  Pprev  =  P  ;  P  =  b  *  Q  -  P  ;  q  =  Q  ;  Q  =  Qprev  +  b  *  (  Pprev  -  P  );  Qprev  =  q  ;  i  ++  ;  }  while  (  P  !=  Föreg  );  r  =  gcd  (  N  ,  Qprev  );  if  (  r  !=  1  &&  r  !=  N  )  returnera  r  ;  }  returnera  ;  } 

•   DA Buell (1989). Binära kvadratiska former . Springer-Verlag. ISBN 0-387-97037-1 .
•   DM Bressoud (1989). Faktorisering och Primalitetstestning . Springer-Verlag. ISBN 0-387-97040-1 .
•   Riesel, Hans (1994). Primtal och datormetoder för faktorisering (2:a uppl.). Birkhauser. ISBN 0-8176-3743-5 .
•   Samuel S. Wagstaff, Jr. (2013). Glädjen med att faktorisera . Providence, RI: American Mathematical Society. s. 163–168. ISBN 978-1-4704-1048-3 .

externa länkar

• Daniel Shanks: Analys och förbättring av den fortsatta fraktionsmetoden för faktorisering , (transkriberad av S. McMath 2004)
• Daniel Shanks: SQUFOF Notes , (transkriberad av S. McMath 2004)
• Stephen S. McMath: Parallell heltalsfaktorisering med kvadratiska former , 2005
• S. McMath, F. Crabbe, D. Joyner: Fortsatt bråk och parallell SQUFOF , 2005
• Jason Gower, Samuel Wagstaff: Square Form Factorization (publicerad)
• Shanks SQUFOF Factoring Algorithm
• java-math-bibliotek