Getallenlichamenzeef
De getallenlichamenzeef is een algoritme om samengestelde getallen te ontbinden in priemfactoren. De basis van deze methode is rond 1988 ontwikkeld door de Britse wiskundige John Pollard, die daarmee het zevende fermatgetal factoriseerde. In de jaren daarna zijn verschillende verbeteringen aangebracht, onder andere door Arjen en Hendrik Lenstra, waardoor het momenteel een van de snelste algoritmen is om een getal te factoriseren. Vooral voor getallen vanaf 100 cijfers is deze methode zeer geschikt; kleinere getallen kunnen sneller met de kwadratische zeef, een eenvoudigere methode om getallen te ontbinden, worden gefactoriseerd.[1]
Geschiedenis
De eerste versie van de getallenlichamenzeef (in het Engels: general number field sieve of GNFS) is bedacht door John Pollard. Deze versie, die de speciale getallenlichamenzeef (in het Engels: special number field sieve of SNFS) heet, kan alleen worden gebruikt voor getallen van de vorm met groot en en klein. Van deze vorm zijn bijvoorbeeld de fermatgetallen. De wiskundigen Joe Buhler en Carl Pomerance bedachten een manier om de speciale getallenlichamenzeef aan te passen, zodat de zeef voor alle getallen (met uitzondering van priemmachten) gebruikt kan worden. Dit leidde tot de algemene getallenlichamenzeef, meestal simpelweg getallenlichamenzeef genoemd.
De eerste getallen die met de speciale getallenlichamenzeef gefactoriseerd werden, zijn , (een getal van 44 cijfers waarvan het ontbinden destijds 47 uur duurde) en (een getal van 47 cijfers dat in 61 uur gefactoriseerd kon worden). Daarnaast is de speciale getallenlichamenzeef gebruikt om onder andere het negende fermatgetal, dat 155 cijfers telt, en mersennepriemgetallen te ontbinden.[2] In januari 2010 heeft een groep wiskundigen een 768-bits RSA-encryptiesleutel weten te kraken met behulp van de getallenlichamenzeef.[3]
Idee
In zekere zin is de getallenlichamenzeef te zien als verbetering van Dixons factorisatiemethode en de kwadratische zeef: men maakt ook hier gebruik van een ontbindingsbasis om gladde factoren te vinden. Daarna wordt eveneens gezocht naar twee getallen die verschillend zijn, maar gekwadrateerd hetzelfde getal opleveren modulo , waar het te factoriseren getal is.
Een verschil met de kwadratische zeef is dat niet langer uitsluitend gewerkt wordt met kwadratische veeltermen. Daarnaast wordt gewerkt over andere getallenlichamen dan de gehele getallen en de gehele getallen modulo , wat als direct gevolg heeft dat de getallenlichamenzeef veel gecompliceerder is dan eerdere methoden.[4]
Achterliggende wiskunde
De kwadratische zeef, waarop de getallenlichamenzeef gebaseerd is, zoekt naar getallen en zodanig dat
Deze getallen worden gevonden door een functie te definiëren en op zoek te gaan naar geschikte getallen , zodat eenvoudig kan worden gevonden als een uitdrukking in deze en kan worden gedefinieerd als het product van de functiewaarden . Feitelijk vervult de functie hier de rol van een ringhomomorfisme, dat kwadraten in de ring afbeeldt op kwadraten in de ring , dit is de ring van gehele getallen modulo . De getallenlichamenzeef gaat uit van hetzelfde idee, maar algemener, door een andere ring dan te gebruiken.[5]
Formeel: zij een ring en een ringhomomorfisme. Als er een is met
dan geldt
In dat geval geldt dat
waaruit direct volgt
Als deze grootste gemene delers niet gelijk zijn aan 1 en , dan hebben we twee niet-triviale factoren gevonden. Op die factoren kunnen we, als ze zelf niet priem zijn, hetzelfde procedé toepassen om een priemfactorontbinding van te verkrijgen. Je kunt met bijvoorbeeld de priemgetaltest bepalen of de gevonden factor priem is.
Keuze van de ring
Iedere polynoom , waarvan de coëfficiënt van de hoogste macht van gelijk aan 1 is en de echte coëfficiënten geheel, rationaal, reëel of complex zijn, is volgens de hoofdstelling van de algebra te schrijven als
met element van de gekozen verzameling, waaruit de coëfficiënten worden gekozen.
Men kan nu een nulpunt van deze polynoom kiezen en de lichaamsuitbreiding bekijken. Deze lichaamsuitbreiding is een lichaam, en kan worden gezien als de verzameling van polynomen in met rationale coëfficiënten, ofwel de -lineaire combinaties van . Het ons beperken tot gehele coëfficiënten, dus -lineaire combinaties, zou als voordeel hebben dat dit eenvoudiger rekent. Er bestaat een ring die we hiervoor kunnen gebruiken.
Een complex getal heet een algebraïsch geheel getal als het een nulpunt is van een polynoom met gehele coëfficiënten, met de coëfficiënt van de hoogste macht van gelijk aan 1. Bij een gegeven van graad met gehele coëfficiënten en een nulpunt kunnen we de verzameling vormen van alle algebraïsch gehele getallen in Deze verzameling vormt een deelring van het lichaam . De verzameling van alle -lineaire combinaties van vormt op zijn beurt weer een deelring van en we noteren hem als . Het is deze ring die we zullen gaan gebruiken.
Een belangrijke propositie[4] zegt namelijk het volgende. Zij op deze manier gedefinieerd, een nulpunt van en zodanig dat
Dan is de afbeelding
die op afbeeldt een surjectief ringhomomorfisme.
Als we zo'n en hebben, kunnen we dus een surjectief ringhomomorfisme construeren. Daarna gaan we dan op zoek naar een verzameling (zie volgende paragraaf) van paren waarvoor geldt dat
en
waarin en .
Hebben we zo'n eenmaal gevonden, dan zijn we klaar, want dan geldt
Het vinden van
Met de bovenstaande paragraaf in het achterhoofd zien we direct dat we een functie moeten kiezen. Daarbij zoeken we dan een nulpunt en een "nulpunt modulo " . Vervolgens willen we een verzameling van geschikte paren vinden. Dat kan door een algebraïsche ontbindingsbasis voor te kiezen (bestaande uit een eindig aantal priemidealen van graad 1 van ) waarover de getallen volledig factoriseren en een rationale ontbindingsbasis (bestaande uit kleine priemgetallen) voor waarover de getallen volledig factoriseren. Als een getal ontbindt over een gekozen ontbindingsbasis, dan noemen we het glad. Als we genoeg paren hebben gevonden waarvoor zowel als glad zijn, dan is er zeker een verzameling te maken bestaande uit (een deel van) de paren zodat
waar en . Hoe dit precies in zijn werk gaat, verschilt niet wezenlijk van de kwadratische zeef.
Met de laatste regels van de vorige paragraaf zijn dan de gewenste getallen , met
te vinden.
Omdat we werken met twee vrij te kiezen variabelen en , wordt vaak vast gekozen en laat men variëren. Daarna hoogt men iets op en zoekt men opnieuw naar geschikte waarden van . Merk op dat voor vaste en vaste voor alle geldt dat
Daaruit volgt dat
- ,
ofwel dat van de vorm met moet zijn. Op deze manier kunnen we veel al wegstrepen als ongeschikt, wat het woord zeef in de naam getallenlichamenzeef verklaart (zie ook zeef van Eratosthenes).
Aanvullende opmerkingen
Al wat nog rest, is het kiezen van een functie , een bijbehorend nulpunt en een zodanig dat
Het is niet bekend wat de beste keuze voor is, noch wat de graad van zou moeten zijn, noch hoe we het beste kunnen vinden. Het algoritme werkt echter ook voor keuzes die niet optimaal zijn, dus is dit ook niet echt van belang. Wel zijn er natuurlijk resultaten over welke waarden het in de praktijk goed doen. Voor getallen van meer dan 110 cijfers leert de ervaring dat goed werkt; voor kleinere getallen zijn (vanaf 80 cijfers) en (vanaf 50 cijfers) beter.[4]
Nu berekent men eerst met de entierfunctie . Dan kan men -tallig schrijven als
- ,
met coëfficiënten voor . De veelterm wordt dan gegeven door
Merk op dat niet irreducibel hoeft te zijn. Als reducibel is, geldt echter dat
voor niet-constante veeltermen en , waaruit volgt dat
waarschijnlijk een niet-triviale factorisatie van is. Als dus reducibel is, dan zijn we nu waarschijnlijk klaar; als dat niet zo is, dan kunnen we de getallenlichamenzeef gebruiken.
Complexiteit
De complexiteit van het algoritme wordt in de O-notatie gegeven door
waarin een constante is met als waarde ongeveer 1,923.
Ter vergelijking: de kwadratische zeef heeft als complexiteit
Hieruit volgt direct dat voor grote men beter de getallenlichamenzeef kan gebruiken om een getal te ontbinden.
- ↑ H.W. Lenstra Jr., Het ontbinden van grote getallen in priemfactoren, Nieuwe Wiskrant 15, september 1995, 7-15
- ↑ A.K. Lenstra en H.W. Lenstra Jr., The development of the number field sieve, Lecture notes in mathematics, Springer-Verlag, Berlijn, 1993
- ↑ T. Kleinjung et al., Factorization of a 768-bit RSA modulus
- ↑ a b c d M.E. Briggs, An Introduction to the General Number Field Sieve, masterscriptie, april 1998
- ↑ C. Pomerance, The number field sieve, Mathematics of Computation, 1943-1993, Fifty Years of Computational Mathematics, W. Gautschi, ed., Proc. Symp. Appl. Math. 48, American Mathematical Society, Providence, 1994, pp. 465-480. Gearchiveerd op 6 mei 2021.