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 $r^{e}-s$ met $e$ groot en $r$ en $|s|$ 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 $2^{128}+1$, $\ \ 2^{144}-3$ (een getal van 44 cijfers waarvan het ontbinden destijds 47 uur duurde) en $2^{153}+3$ (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 $N$, waar $N$ 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 $N$, 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 $x$ en $y$ zodanig dat

$x^{2}\equiv y^{2}{\pmod {N}}\quad {\mbox{ en }}x\neq \pm y$

Deze getallen worden gevonden door een functie $\phi$ te definiëren en op zoek te gaan naar geschikte getallen $x_{i}$, zodat $x^{2}$ eenvoudig kan worden gevonden als een uitdrukking in deze $x_{i}$ en $y^{2}$ kan worden gedefinieerd als het product van de functiewaarden $\phi (x_{i})$. Feitelijk vervult de functie $\phi$ hier de rol van een ringhomomorfisme, dat kwadraten in de ring $\mathbb {Z}$ afbeeldt op kwadraten in de ring $\mathbb {Z} /N\mathbb {Z}$, dit is de ring van gehele getallen modulo $N$. De getallenlichamenzeef gaat uit van hetzelfde idee, maar algemener, door een andere ring dan $\mathbb {Z}$ te gebruiken.

Formeel: zij $R$ een ring en $\phi :R\to \mathbb {Z} /N\mathbb {Z}$ een ringhomomorfisme. Als er een $r\in R$ is met

$\phi (r^{2})=y^{2}{\pmod {N}}\quad {\mbox{ en }}\quad x=\phi (r),$

dan geldt

$x^{2}\equiv \phi (r)^{2}\equiv \phi (r^{2})\equiv y^{2}{\pmod {N}}$

In dat geval geldt dat

$x^{2}-y^{2}\equiv 0{\pmod {N}},$

waaruit direct volgt

$N=\mathrm {ggd} (N,\ x^{2}-y^{2})|\mathrm {ggd} (N,\ x-y)\cdot \mathrm {ggd} (N,\ x+y)$

Als deze grootste gemene delers niet gelijk zijn aan 1 en $N$, 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 $N$ te verkrijgen. Je kunt met bijvoorbeeld de priemgetaltest bepalen of de gevonden factor priem is.

Keuze van de ring

Iedere polynoom $f(x)=x^{n}+a_{n-1}x^{n-1}+\ldots +a_{0}$, waarvan de coëfficiënt van de hoogste macht van $x$ 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

$f(x)=(x-\theta _{1})(x-\theta _{2})\cdots (x-\theta _{d}),$

met $\theta _{i}$ element van de gekozen verzameling, waaruit de coëfficiënten worden gekozen.

Men kan nu een nulpunt $\vartheta$ van deze polynoom kiezen en de lichaamsuitbreiding $\mathbb {Q} (\vartheta )$ bekijken. Deze lichaamsuitbreiding is een lichaam, en kan worden gezien als de verzameling van polynomen in $\vartheta$ met rationale coëfficiënten, ofwel de $\mathbb {Q}$-lineaire combinaties van $\{1,\vartheta ,\vartheta ^{2},\ldots ,\vartheta ^{d-1}\}$. Het ons beperken tot gehele coëfficiënten, dus $\mathbb {Z}$-lineaire combinaties, zou als voordeel hebben dat dit eenvoudiger rekent. Er bestaat een ring die we hiervoor kunnen gebruiken.

Een complex getal $\alpha$ heet een algebraïsch geheel getal als het een nulpunt is van een polynoom $f(x)$ met gehele coëfficiënten, met de coëfficiënt van de hoogste macht van $x$ gelijk aan 1. Bij een gegeven $f(x)$ van graad $d$ met gehele coëfficiënten en een nulpunt $\vartheta \in \mathbb {C}$ kunnen we de verzameling $R[\vartheta ]$ vormen van alle algebraïsch gehele getallen in $\mathbb {Q} (\vartheta ).$ Deze verzameling vormt een deelring van het lichaam $\mathbb {Q} (\vartheta )$. De verzameling van alle $\mathbb {Z}$-lineaire combinaties van $\{1,\vartheta ,\vartheta ^{2},\ldots ,\vartheta ^{d-1}\}$ vormt op zijn beurt weer een deelring van $R[\theta ]$ en we noteren hem als $\mathbb {Z} [\theta ]$. Het is deze ring die we zullen gaan gebruiken.

Een belangrijke propositie zegt namelijk het volgende. Zij $f(x)$ op deze manier gedefinieerd, $\vartheta \in \mathbb {C}$ een nulpunt van $f(x)$ en $m\in \mathbb {Z} /N\mathbb {Z}$ zodanig dat

$f(m)\equiv 0{\pmod {N}}$

Dan is de afbeelding

$\phi :\mathbb {Z} [\vartheta ]\to \mathbb {Z} /N\mathbb {Z}$

die $\vartheta$ op $m$ afbeeldt een surjectief ringhomomorfisme.

Als we zo'n $f,\,\vartheta$ en $m$ hebben, kunnen we dus een surjectief ringhomomorfisme $\phi$ construeren. Daarna gaan we dan op zoek naar een verzameling $U$ (zie volgende paragraaf) van paren $(a,b)$ waarvoor geldt dat

$\prod _{(a,b)\in U}(a+b\vartheta )=\beta ^{2}$

en

$\prod _{(a,b)\in U}(a+bm)=y^{2},$

waarin $\beta \in \mathbb {Z} [\vartheta ]$ en $y\in \mathbb {Z}$.

Hebben we zo'n $U$ eenmaal gevonden, dan zijn we klaar, want dan geldt

$x^{2}\equiv \phi (\beta )^{2}\equiv \phi (\beta ^{2})\equiv \phi \left(\prod _{(a,b)\in U}(a+b\vartheta )\right)\equiv \prod _{(a,b)\in U}\phi (a+b\vartheta )\equiv \prod _{(a,b)\in U}(a+bm)\equiv y^{2}{\pmod {N}}.$

Het vinden van $U$

Met de bovenstaande paragraaf in het achterhoofd zien we direct dat we een functie $f$ moeten kiezen. Daarbij zoeken we dan een nulpunt $\vartheta$ en een "nulpunt modulo $N$" $m$. Vervolgens willen we een verzameling $U$ van geschikte paren $(a,b)$ vinden. Dat kan door een algebraïsche ontbindingsbasis $I$ voor $\mathbb {Z} [\vartheta ]$ te kiezen (bestaande uit een eindig aantal priemidealen van graad 1 van $\mathbb {Z} [\theta ]$) waarover de getallen $a+b\vartheta$ volledig factoriseren en een rationale ontbindingsbasis $F$ (bestaande uit kleine priemgetallen) voor $\mathbb {Z}$ waarover de getallen $a+bm$ volledig factoriseren. Als een getal ontbindt over een gekozen ontbindingsbasis, dan noemen we het glad. Als we genoeg paren $(a,b)$ hebben gevonden waarvoor zowel $a+b\vartheta$ als $a+bm$ glad zijn, dan is er zeker een verzameling $U$ te maken bestaande uit (een deel van) de paren $(a,b)$ zodat

$\prod _{(a,b)\in U}(a+b\vartheta )=\beta ^{2}\quad {\textrm {en}}\quad \prod _{(a,b)\in U}(a+bm)=y^{2},$

waar $\beta \in \mathbb {Z} [\vartheta ]$ en $y\in \mathbb {Z}$. 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 $x$, $y$ met

$x^{2}\equiv y^{2}{\pmod {N}}\quad {\mbox{ en }}x\neq \pm y$

te vinden.

Omdat we werken met twee vrij te kiezen variabelen $a$ en $b$, wordt vaak $b=1$ vast gekozen en laat men $a$ variëren. Daarna hoogt men $b$ iets op en zoekt men opnieuw naar geschikte waarden van $a$. Merk op dat voor vaste $p\in F$ en vaste $b$ voor alle $a\in \mathbb {Z}$ geldt dat

$p\mid a+bm\iff a+bm\equiv 0{\pmod {p}}$

Daaruit volgt dat

$a\equiv -bm{\pmod {p}}$,

ofwel dat $a$ van de vorm $a=-bm+kp$ met $k\in \mathbb {Z}$ moet zijn. Op deze manier kunnen we veel $a$ 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 $f$, een bijbehorend nulpunt $\vartheta$ en een $m\in \mathbb {Z}$ zodanig dat

$f(m)\equiv 0{\pmod {N}}$

Het is niet bekend wat de beste keuze voor $f$ is, noch wat de graad van $f$ zou moeten zijn, noch hoe we $m$ 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 $d=5$ goed werkt; voor kleinere getallen zijn $d=4$ (vanaf 80 cijfers) en $d=3$ (vanaf 50 cijfers) beter.

Nu berekent men eerst met de entierfunctie $m=\lfloor N^{1/d}\rfloor$. Dan kan men $N$ $m$-tallig schrijven als

$N=m^{d}+a_{d-1}m^{d-1}+\ldots +a_{1}m+a_{0}$,

met coëfficiënten $0\leq a_{i}<m$ voor $0\leq i<d$. De veelterm $f$ wordt dan gegeven door

$f(x)=x^{d}+a_{d-1}x^{d-1}+\ldots +a_{1}x+a_{0}$

Merk op dat $f$ niet irreducibel hoeft te zijn. Als $f$ reducibel is, geldt echter dat

$f(x)=g(x)\cdot h(x)$

voor niet-constante veeltermen $g$ en $h$, waaruit volgt dat

$N=f(m)=g(m)\cdot h(m)$

waarschijnlijk een niet-triviale factorisatie van $N$ is. Als $f$ 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

$O\left(e^{c\,(\ln {n})^{1/3}(\ln {\ln {n}})^{2/3}}\right),$

waarin $c$ een constante is met als waarde ongeveer 1,923.

Ter vergelijking: de kwadratische zeef heeft als complexiteit

$O\left(\mathrm {e} ^{(\ln {n})^{1/2}(\ln {\ln {n}})^{1/2}}\right).$

Hieruit volgt direct dat voor grote $n$ men beter de getallenlichamenzeef kan gebruiken om een getal te ontbinden.

Bronnen, noten en/of referenties