Dixons faktoriseringsmetod - Dixon's factorization method

I talteori , Dixons faktorisering metod (även Dixons slumpmässig kvadratmetoden eller Dixons algoritm ) är ett allmänt ändamål primtalsfaktorisering algoritm ; det är den prototypiska faktorbasmetoden . Till skillnad från andra faktorbasmetoder kommer dess körning med ett strikt bevis som inte förlitar sig på antaganden om jämnhetsegenskaperna för värden som tas av polynom.

Algoritmen designades av John D. Dixon , en matematiker vid Carleton University , och publicerades 1981.

Grundläggande idé

Dixons metod bygger på att hitta en kongruens av kvadrater modulo det heltal N som är avsett att faktor. Fermats faktoriseringsmetod hittar en sådan kongruens genom att välja slumpmässiga eller pseudoslumpmässiga x- värden och hoppas att heltalet x ² mod N är ett perfekt kvadrat (i heltal):

{\ displaystyle x ^ {2} \ equiv y ^ {2} \ quad ({\ hbox {mod}} N), \ qquad x \ not \ equiv \ pm y \ quad ({\ hbox {mod}} N) .}

Till exempel, om N = 84923 , (genom att börja vid 292, den första siffran större än √ N och räkna upp) är 505 ² mod 84923 256, kvadraten av 16. Så (505 - 16) (505 + 16) = 0 mod 84923 . Beräkna den största gemensamma delaren av 505-16 och N med användning av Euklides algoritm ger 163, som är en faktor av N .

I praktiken väljer slump x kommer värden att ta en opraktiskt lång tid att hitta en kongruens av kvadrater, eftersom det bara finns √ N rutor mindre än N .

Dixons metod ersätter villkoret "är kvadraten för ett heltal" med det mycket svagare "har bara små primära faktorer"; till exempel finns det 292 rutor mindre än 84923; 662 siffror mindre än 84923 vars huvudfaktorer bara är 2,3,5 eller 7; och 4767 vars huvudfaktorer alla är mindre än 30. (Sådana tal kallas B-släta med avseende på vissa bundna B. )

Om det finns många tal vars kvadrater kan faktoriseras som för en fast uppsättning små primtal, kommer linjär algebra modulo 2 på matrisen att ge en delmängd av vars kvadrater kombineras till en produkt med små primtal till en jämn effekt - det vill säga en delmängd av vars kvadrater multipliceras med kvadraten för ett (förhoppningsvis annorlunda) tal mod N. ${\ displaystyle a_ {1} \ ldots a_ {n}}$ ${\ displaystyle a_ {i} ^ {2} \ mod N = \ prod _ {j = 1} ^ {m} b_ {j} ^ {e_ {ij}}}$ ${\ displaystyle b_ {1} \ ldots b_ {m}}$ ${\ displaystyle e_ {ij}}$ ${\ displaystyle a_ {i}}$ ${\ displaystyle a_ {i}}$

Metod

Antag att det sammansatta numret N tas med i beräkningen. Bundna B väljs, och faktorbas identifieras (vilket kallas P ), mängden av alla primtal mindre än eller lika med B . Nästa, positiva heltal z söks så att z ² mod N är B -smooth. Därför kan det skrivas, för lämpliga exponenter a _i ,

{\ displaystyle z ^ {2} {\ text {mod}} N = \ prod _ {p_ {i} \ i P} p_ {i} ^ {a_ {i}}}

När tillräckligt med dessa relationer har genererats (det är i allmänhet tillräckligt att antalet relationer är några fler än storleken på P ), kan metoderna för linjär algebra användas (till exempel Gaussisk eliminering ) för att multiplicera tillsammans dessa olika relationer på ett sådant sätt att exponenterna av premiärerna på höger sida alla är jämna:

{\ displaystyle {z_ {1} ^ {2} z_ {2} ^ {2} \ cdots z_ {k} ^ {2} \ equiv \ prod _ {p_ {i} \ in P} p_ {i} ^ { a_ {i, 1} + a_ {i, 2} + \ cdots + a_ {i, k}} \ {\ pmod {N}} \ quad ({\ text {där}} a_ {i, 1} + a_ {i, 2} + \ cdots + a_ {i, k} \ equiv 0 {\ pmod {2}})}}

Detta ger en kongruens av kvadrater av formen en ^två ≡ b ² (mod N ), som kan omvandlas till en faktorisering av N , N = gcd ( a + b , N ) x ( N / gcd ( a + b , N )). Denna faktorisering kan visa sig vara trivial (dvs. N = N × 1 ), vilket bara kan hända om a ≡ ± b (mod N ), i vilket fall ett nytt försök måste göras med en annan kombination av relationer; men ett icke-trivialt par faktorer av N kan nås, och algoritmen kommer att avslutas.

Pseudokod

input: positive integer  ${\textstyle N}$ 
output: non-trivial factor of  ${\textstyle N}$ 

Choose bound  ${\textstyle B}$ 
Let  ${\textstyle P:=\{p_{1},p_{2},\ldots ,p_{k}\}}$  be all primes  ${\textstyle \leq B}$ 

repeat
    for  ${\textstyle i=1}$  to  ${\textstyle k+1}$  do
        Choose  ${\textstyle 0<z_{i}<N}$  such that  ${\textstyle z_{i}^{2}{\text{ mod }}N}$  is  ${\textstyle B}$ -smooth
        Let  ${\textstyle a_{i}:=\{a_{i1},a_{i2},\ldots ,a_{ik}\}}$  such that  ${\textstyle z_{i}^{2}{\text{ mod }}N=\prod _{p_{j}\in P}p_{j}^{a_{ij}}}$ 
    end for

    Find non-empty  ${\textstyle T\subseteq \{1,2,\ldots ,k+1\}}$  such that  ${\textstyle \sum _{i\in T}a_{i}\equiv {\vec {0}}{\pmod {2}}}$ 
    Let  ${\textstyle x:=\left(\prod _{i\in T}z_{i}\right){\text{ mod }}N}$ 
         ${\textstyle y:=\left(\prod _{p_{j}\in P}p_{j}^{\left(\sum _{i\in T}a_{ij}\right)/2}\right){\text{ mod }}N}$ 
while  ${\textstyle x\equiv \pm y{\pmod {N}}}$  

return  ${\textstyle \gcd(x+y,N)}$

Exempel

Detta exempel kommer att försöka faktor N = 84.923 användning bundet B = 7. faktorbas är då P = {2, 3, 5, 7}. En sökning kan göras för heltal mellan och N vars rutor mod N är B- släta . Antag att två av siffrorna som hittades är 513 och 537: ${\ displaystyle \ left \ lceil {\ sqrt {84923}} \ right \ rceil = 292}$

{\ displaystyle 513 ^ {2} \ mod 84923 = 8400 = 2 ^ {4} \ cdot 3 \ cdot 5 ^ {2} \ cdot 7}

{\ displaystyle 537 ^ {2} \ mod 84923 = 33600 = 2 ^ {6} \ cdot 3 \ cdot 5 ^ {2} \ cdot 7}

Så

{\ displaystyle (513 \ cdot 537) ^ {2} \ mod 84923 = 2 ^ {10} \ cdot 3 ^ {2} \ cdot 5 ^ {4} \ cdot 7 ^ {2} \ mod 84923}

Sedan

${\ displaystyle {\ begin {align} & {} (513 \ cdot 537) ^ {2} \ mod 84923 \\ & = (275481) ^ {2} \ mod 84923 \\ & = (84923 \ cdot 3 + 20712 ) ^ {2} \ mod 84923 \\ & = (84923 \ cdot 3) ^ {2} +2 \ cdot (84923 \ cdot 3 \ cdot 20712) + 20712 ^ {2} \ mod 84923 \\ & = 0+ 0 + 20712 ^ {2} \ mod 84923 \ end {align}}}$

Det är, ${\ displaystyle 20712 ^ {2} \ mod 84923 = (2 ^ {5} \ cdot 3 \ cdot 5 ^ {2} \ cdot 7) ^ {2} \ mod 84923 = 16800 ^ {2} \ mod 84923.}$

Den resulterande faktoriseringen är 84923 = gcd (20712 - 16800, 84923) × gcd (20712 + 16800, 84923) = 163 × 521.

Optimeringar

Den kvadratiska sikten är en optimering av Dixons metod. Det väljer värden på x nära kvadratroten för N så att x ² modulo N är liten, vilket därigenom till stor del ökar chansen att få ett jämnt antal.

Andra sätt att optimera Dixons metod inkluderar att använda en bättre algoritm för att lösa matrisekvationen och dra nytta av matrisens sparsitet: ett tal z kan inte ha mer än faktorer, så varje rad i matrisen är nästan alla nollor. I praktiken används ofta block-Lanczos-algoritmen . Storleken på faktorbasen måste också väljas noggrant: om den är för liten blir det svårt att hitta siffror som faktoriserar helt över den, och om den är för stor måste fler relationer samlas in. ${\ displaystyle \ log _ {2} z}$

En mer sofistikerad analys, med användning av approximationen att ett tal har alla sina primära faktorer mindre än med sannolikhet omkring (en approximation till Dickman – de Bruijn-funktionen ), indikerar att valet av för liten faktorbas är mycket sämre än för stor, och att den ideala faktorbasstorleken är viss kraft . ${\ displaystyle N ^ {1 / a}}$ ${\ displaystyle a ^ {- a}}$ ${\ displaystyle \ exp \ left ({\ sqrt {\ log N \ log \ log N}} \ right)}$