Generelt nummerfelt sigte - General number field sieve

I talteori er den generelle talfelt sigte ( GNFS ) den mest effektive klassiske algoritme kendt for factoring af heltal større end 10 100 . Heuristisk er dens kompleksitet for faktorering af et heltal n (bestående af ⌊log 2 n ⌋ + 1 bit) af formen

(i L-notation ), hvor ln er den naturlige logaritme . Det er en generalisering af det specielle talfelt sigte : mens sidstnævnte kun kan faktorere tal i en bestemt speciel form, kan det generelle talfelt sigte faktorere et hvilket som helst tal bortset fra primære kræfter (som er trivielle for faktor ved at tage rødder).

Princippet om nummerfeltsigte (både specielt og generelt) kan forstås som en forbedring af den enklere rationelle sigte eller kvadratisk sigte . Når man bruger sådanne algoritmer til at faktorere et stort antal n , er det nødvendigt at søge efter glatte tal (dvs. tal med små primfaktorer) af orden n 1/2 . Størrelsen på disse værdier er eksponentiel i størrelsen n (se nedenfor). Den generelle talfelt sigte klarer derimod at søge efter glatte tal, der er undereksponentielle i størrelsen n . Da disse tal er mindre, er de mere tilbøjelige til at være glatte end de tal, der blev inspiceret i tidligere algoritmer. Dette er nøglen til effektiviteten af ​​nummerfeltets sigte. For at opnå denne hastighed skal nummerfeltets sigte udføre beregninger og faktoriseringer i antal felter . Dette resulterer i mange ret komplicerede aspekter af algoritmen sammenlignet med den enklere rationelle sigte.

Størrelsen af ​​input til algoritmen er log 2   n eller antallet af bits i den binære repræsentation af n . Enhver element i orden n c for en konstant c er eksponentiel i log  n . Kørselstiden for nummerfeltets sigte er superpolynomisk, men subeksponentiel i størrelsen af ​​inputet.

Antal felter

Hovedartikel: Nummerfelt

Antag at f er et k- grad polynomium over Q (de rationelle tal), og r er en kompleks rod af f . Derefter er f ( r ) = 0 , som kan omarrangeres til at udtrykke r k som en lineær kombination af kræfter på r mindre end k . Denne ligning kan bruges til at reducere alle kræfter fra r med eksponent e ≥ k . For eksempel, hvis f ( x ) =  x 2  + 1 og r er den imaginære enhed i , så er i 2  + 1 = 0 eller i 2  = -1 . Dette giver os mulighed for at definere det komplekse produkt:

Generelt fører dette direkte til det algebraiske talfelt Q [ r ] , som kan defineres som det sæt af komplekse tal givet ved:

Produktet af en hvilken som helst to sådanne værdier kan beregnes ved at tage produktet som polynomer og derefter reducere eventuelle kræfter for r med eksponent e ≥ k som beskrevet ovenfor, hvilket giver en værdi i samme form. For at sikre, at dette felt faktisk er k -dimensionalt og ikke kollapser til et endnu mindre felt, er det tilstrækkeligt, at f er et irreducerbart polynom over forholdene. Tilsvarende kan man definere ringen af ​​heltal O Q [ r ] som delmængde af Q [ r ], som er rødder af moniske polynomer med heltalskoefficienter. I nogle tilfælde svarer denne ring af heltal til ringen Z [ r ] . Der er dog mange undtagelser, såsom for Q [ √ d ] når d er lig med 1 modulo 4.

Metode

To polynomier f ( x ) og g ( x ) med små grader d og e vælges, som har heltalskoefficienter, som er irreducerbare i forhold til rationelle , og som, når de fortolkes mod n , har et fælles heltal rod m . En optimal strategi til valg af disse polynomer er ikke kendt; en enkel metode er at vælge en grad d for et polynom, overveje udvidelsen af n i basis m (tillader cifre mellem - m og m ) for et antal forskellige m af rækkefølge n 1 / d og vælge f ( x ) som polynomet med de mindste koefficienter og g ( x ) som x  -  m .

Overvej talfeltringene Z [ r 1 ] og Z [ r 2 ], hvor r 1 og r 2 er rødderne til polynomerne f og g . Da f er af grad d med heltalskoefficienter, hvis a og b er heltal, så vil det være b d · f ( a / b ), som vi kalder r . Tilsvarende er s = b e · g ( a / b ) et heltal. Målet er at finde heltalsværdier af a og b, der samtidig gør r og s glatte i forhold til det valgte basis for primtal. Hvis a og b er små, vil r og s også være små, omtrent på størrelse med m , og vi har en bedre chance for, at de bliver glatte på samme tid. Den nuværende bedst kendte tilgang til denne søgning er gittersigtning ; for at opnå acceptable udbytter er det nødvendigt at bruge en stor faktorbase.

Når man har nok sådanne par, ved hjælp af Gaussisk eliminering , kan man få produkter af bestemt r og af de tilsvarende s til at være kvadrater på samme tid. Der er behov for en lidt stærkere tilstand - at de er normer for kvadrater i vores antal felter, men denne betingelse kan også opnås ved denne metode. Hver r er en norm af en  -  r 1 b og dermed, at produktet af de tilsvarende faktorer a  -  r 1 b er et kvadrat i Z [ r 1 ], med en "kvadratroden", som kan bestemmes (som et produkt af kendte faktorer i Z [ r 1 ]) - det vil typisk blive repræsenteret som et irrationelt algebraisk tal . Tilsvarende produktet af faktorerne en  -  r 2 b er en firkant i Z [ r 2 ], med en "kvadratroden", der også kan beregnes. Det skal bemærkes, at brugen af ​​Gaussisk eliminering ikke giver algoritmens optimale driftstid. I stedet anvendes sparsomme matrixløsningsalgoritmer som Block Lanczos eller Block Wiedemann .

Da m er en rod af både f og g mod n , er der homomorfier fra ringene Z [ r 1 ] og Z [ r 2 ] til ringen Z / n Z (heltal mod n ), som kortlægger r 1 og r 2 til m , og disse homomorfier kortlægger hver "kvadratrod" (typisk ikke repræsenteret som et rationelt tal) i dets heltalrepræsentant. Nu kan produktet af faktorerne a  -  mb mod n opnås som et kvadrat på to måder - en for hver homomorfisme. Således kan man finde to tal x og y , med x 2  -  y 2 delelig med n og igen med sandsynlighed mindst halvdelen får vi en faktor n ved at finde den største fællesdeler af n og x  -  y .

Forbedring af polynomvalg

Valget af polynom kan dramatisk påvirke tiden til at fuldføre resten af ​​algoritmen. Metoden til valg af polynomer baseret på udvidelsen af n i base m vist ovenfor er suboptimal i mange praktiske situationer, hvilket fører til udvikling af bedre metoder.

En sådan metode blev foreslået af Murphy og Brent; de introducerer en todelt score for polynomer baseret på tilstedeværelsen af ​​rødder modulo små primtal og på den gennemsnitlige værdi, som polynomet overtager sigteområdet.

De bedst rapporterede resultater blev opnået ved hjælp af metoden fra Thorsten Kleinjung , som tillader g ( x ) = ax  +  b , og søger over en sammensat af små primfaktorer, der er kongruente til 1 modulo 2 d og over ledende koefficienter af f, som er delelige med 60 .

Implementeringer

Nogle implementeringer fokuserer på en bestemt mindre klasse af tal. Disse er kendt som specielle nummersystemer , som anvendes i Cunningham-projektet . Et projekt kaldet NFSNET løb fra 2002 gennem mindst 2007. Det brugte frivilligt distribueret computing på Internettet . Paul Leyland fra Det Forenede Kongerige og Richard Wackerbarth fra Texas var involveret.

Indtil 2007 var guldstandardimplementeringen en suite software udviklet og distribueret af CWI i Holland, som kun var tilgængelig under en relativt restriktiv licens. I 2007 udviklede Jason Papadopoulos en hurtigere implementering af den endelige behandling som en del af msieve, som er i det offentlige domæne. Begge implementeringer har muligheden for at blive distribueret mellem flere noder i en klynge med en tilstrækkelig hurtig sammenkobling.

Valg af polynomer udføres normalt af GPL- software skrevet af Kleinjung eller af msieve og gittersigtning af GPL-software skrevet af Franke og Kleinjung; disse distribueres i GGNFS.

Se også

Bemærkninger

Referencer

  • Matthew E. Briggs: En introduktion til det generelle antal feltsigte, 1998