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.

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. In januari 2010 heeft een groep wiskundigen een 768-bits RSA-encryptiesleutel weten te kraken met behulp van de getallenlichamenzeef.

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.

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.

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 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.

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.

Algoritme