Allmänt nummer fältsil

I talteorin är GNFS ( general number field sieve) den mest effektiva klassiska algoritmen som är känd för att faktorisera heltal större än 10 ¹⁰⁰ . Heuristiskt sett är dess komplexitet för att faktorisera ett heltal n (bestående av ⌊log ₂ n ⌋ + 1 bitar) av formen

$\exp \left(\ vänster({\sqrt[{3}]{\frac {64}{9}}}+o(1)\right)(\ln n)^{\frac {1}{3}}(\ln \ln n)^{\frac {2}{3}}\right)=L_{n}\vänster[{\frac {1}{3}},{\sqrt[{3}]{\frac {64}{ 9}}}\höger]$

(i L-notation ), där ln är den naturliga logaritmen . Det är en generalisering av specialtalfältsilen : medan den senare bara kan faktorisera tal av en viss speciell form, kan den allmänna talfältsilen faktorisera vilket tal som helst förutom primpotenser (som är triviala att faktorisera genom att slå rötter).

Principen för nummerfältssilen (både speciell och generell) kan förstås som en förbättring av den enklare rationella sikten eller kvadratsikten . När man använder sådana algoritmer för att faktorisera ett stort antal n , är det nödvändigt att söka efter jämna tal (dvs. tal med små primtalsfaktorer) av ordningen n ^1/2 . Storleken på dessa värden är exponentiell i storleken n (se nedan). Den allmänna talfältssilen lyckas å andra sidan söka efter jämna tal som är subexponentiella i storleken n . Eftersom dessa siffror är mindre är det mer sannolikt att de är jämna än siffrorna som inspekterades i tidigare algoritmer. Detta är nyckeln till effektiviteten hos nummerfältssilen. För att uppnå denna snabbhet måste talfältssilen utföra beräkningar och faktoriseringar i talfält . Detta resulterar i många ganska komplicerade aspekter av algoritmen, jämfört med den enklare rationella sållen.

Storleken på indata till algoritmen är log _2n   av eller antalet bitar i den binära representationen n . Varje element av ordningen n ^c för en konstant c är exponentiellt i log n . Körtiden för nummerfältssilen är superpolynom men subexponentiell i storleken på inmatningen.

Nummerfält

Huvudartikel: Nummerfält

Antag att f är ett k -graders polynom över Q (de rationella talen), och r är en komplex rot av f . Sedan är f ( r ) = 0 , som kan omarrangeras för att uttrycka r ^k som en linjär kombination av potenser av r mindre än k . Denna ekvation kan användas för att reducera bort eventuella potenser av r med exponent e ≥ k . Till exempel, om f ( x ) = x ² + 1 och r är den imaginära enheten i , då i ² + 1 = 0 , eller i ² = −1 . Detta gör att vi kan definiera den komplexa produkten:

$(a+bi)(c+di)=ac+(ad+bc)i+(bd)i^{2}=(ac-bd)+(ad+bc)i.$

I allmänhet leder detta direkt till det algebraiska talfältet Q [ r ] , som kan definieras som mängden komplexa tal som ges av:

$a_{k-1}r^{k-1}+...+a_{1}r^{1}+a_{0}r^{0},{\text{ där }}a_{ 0},...,a_{k-1}{\text{ i }}\mathbf {Q} .$

Produkten av två sådana värden kan beräknas genom att ta produkten som polynom och sedan reducera eventuella potenser av r med exponent e ≥ k som beskrivits ovan, vilket ger ett värde i samma form. För att säkerställa att detta fält faktiskt är k -dimensionellt och inte kollapsar till ett ännu mindre fält, är det tillräckligt att f är ett irreducerbart polynom över rationalerna. På liknande sätt kan man definiera ringen av heltal O _{Q [ r ]} som delmängden av Q [ r ] som är rötter till moniska polynom med heltalskoefficienter. I vissa fall är denna ring av heltal ekvivalent med ringen Z [ r ] . Det finns dock många undantag, som för Q [ √ d ] när d är lika med 1 modulo 4.

Metod

Två polynom f ( x ) och g ( x ) med små grader d och e väljs, som har heltalskoefficienter, som är irreducerbara över rationalerna , och som, när de tolkas mod n , har en gemensam heltalsrot m . En optimal strategi för att välja dessa polynom är inte känd; en enkel metod är att välja en grad d för ett polynom, betrakta expansionen av n i basen m (tillåter siffror mellan − m och m ) för ett antal olika m av ordningen n ^{1/ d} , och välj f ( x ) som polynomet med de minsta koefficienterna och g ( x ) som x − m .

Betrakta talfältsringarna Z [ r ₁ ] och Z [ r ₂ ], där r ₁ och r ₂ är rötter till polynomen f och g . Eftersom f är av grad d med heltalskoefficienter, om a och b är heltal, så kommer det att vara b ^d · f ( a / b ), som vi kallar r . På liknande sätt s = b ^e · g ( a / b ) ett heltal. Målet är att hitta heltalsvärden för a och b som samtidigt gör r och s jämna i förhållande till den valda basen av primtal. Om a och b är små, så kommer r och s också att vara små, ungefär lika stora som m , och vi har större chans att de blir jämna samtidigt. Den för närvarande mest kända metoden för denna sökning är gittersiktning ; för att få acceptabel avkastning är det nödvändigt att använda en stor faktorbas.

Om man har tillräckligt med sådana par, med hjälp av Gaussisk eliminering , kan man få produkter av vissa r och av motsvarande s att vara kvadrater samtidigt. Det behövs ett lite starkare villkor – att de är normer för kvadrater i våra talfält, men det villkoret kan uppnås med denna metod också. Varje r är en norm av a − r ₁ b och därmed att produkten av motsvarande faktorer a − r ₁ b är en kvadrat i Z [ r ₁ ], med en "kvadratrot" som kan bestämmas (som en produkt av kända faktorer i Z [ r ₁ ])—det kommer vanligtvis att representeras som ett irrationellt algebraiskt tal . På liknande sätt är produkten av faktorerna a − r ₂ b en kvadrat i Z [ r ₂ ], med en "kvadratrot" som också kan beräknas. Det bör noteras att användningen av Gaussisk eliminering inte ger den optimala körtiden för algoritmen. används glesa matrislösningsalgoritmer som Block Lanczos eller Block Wiedemann .

Eftersom m är en rot av både f och g mod n finns det homomorfismer från ringarna Z [ r ₁ ] och Z [ r ₂ ] till ringen Z / n Z (heltalen modulo n ), som mappar r ₁ och r ₂ till m , och dessa homomorfismer kommer att mappa varje "kvadratrot" (vanligtvis inte representerad som ett rationellt tal) till dess heltalsrepresentant. Nu kan produkten av faktorerna a − mb mod n erhållas som en kvadrat på två sätt - en för varje homomorfism. Man kan alltså hitta två tal x och y , med x ² − y ² delbart med n och återigen med sannolikhet minst hälften får vi en faktor på n genom att hitta den största gemensamma delaren av n och x − y .

Förbättring av polynomval

Valet av polynom kan dramatiskt påverka tiden för att slutföra resten av algoritmen. Metoden för att välja polynom baserat på expansionen av n i basen m som visas ovan är suboptimal i många praktiska situationer, vilket leder till utvecklingen av bättre metoder.

En sådan metod föreslogs av Murphy och Brent; de introducerar en tvådelad poäng för polynom, baserad på närvaron av rötter modulo små primtal och på det genomsnittliga värdet som polynomet tar över siktningsområdet.

De bästa rapporterade resultaten uppnåddes med metoden av Thorsten Kleinjung, som tillåter g ( x ) = ax + b , och sökningar över en sammansatt av små primtalsfaktorer kongruenta med 1 modulo 2 d och över ledande koefficienter för f som är delbara med 60 .

Genomföranden

Vissa implementeringar fokuserar på en viss mindre klass av nummer. Dessa är kända som specialnummerfältsålltekniker , såsom de används i Cunningham-projektet . Ett projekt kallat NFSNET pågick från 2002 till åtminstone 2007. Det använde frivilligt distribuerad datoranvändning på Internet . Paul Leyland från Storbritannien och Richard Wackerbarth från Texas var inblandade.

Fram till 2007 var implementeringen av guldstandarden en uppsättning mjukvara utvecklad och distribuerad av CWI i Nederländerna, som endast var tillgänglig under en relativt restriktiv licens. År 2007 utvecklade Jason Papadopoulos en snabbare implementering av slutbehandling som en del av msieve, som är allmän egendom. Båda implementeringarna har möjligheten att fördelas mellan flera noder i ett kluster med en tillräckligt snabb sammankoppling.

Polynomval utförs normalt av GPL -mjukvara skriven av Kleinjung, eller av msieve, och gittersiktning av GPL-mjukvara skriven av Franke och Kleinjung; dessa distribueras i GGNFS.

• NFS@Home
• GGNFS
• faktor av gnfs
• CADO-NFS
• msieve (som innehåller slutbearbetningskod, ett polynomval optimerat för mindre antal och en implementering av linjesilen)
• kmGNFS

Se även

• Specialnummerfältsåll

Anteckningar

• Arjen K. Lenstra och HW Lenstra, Jr. (red.). "Utvecklingen av nummerfältssilen". Föreläsningsanteckningar i matematik. (1993) 1554. Springer-Verlag.
•   Richard Crandall och Carl Pomerance . Prime Numbers: A Computational Perspective (2001). 2:a upplagan, Springer. ISBN 0-387-25282-7 . Avsnitt 6.2: Nummerfältsåll, s. 278–301.

• Matthew E. Briggs: An Introduction to the General Number Field Sieve, 1998