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 tegenwoordig een van de snelste algoritmen is om grote getallen te factoriseren. Vooral voor getallen vanaf 100 cijfers is deze methode zeer geschikt. Voor kleinere getallen is de kwadratische zeef doorgaans eenvoudiger.

Een priemgetaltest is een algoritme dat bepaalt of een gegeven getal al dan niet een priemgetal is. De werking van een priemgetaltest en een getallenlichamenzeef komt op hetzelfde neer, maar men noemt het in de meer ontwikkelde theorie, waarbij de complexiteitsgraad van de verschillende algoritmen met elkaar wordt vergeleken, een getallenlichamenzeef.

Geschiedenis

De eerste variant van de getallenlichamenzeef, ontwikkeld door John Pollard, wordt de speciale getallenlichamenzeef genoemd. Deze kan alleen worden toegepast op getallen van de vorm $r^{e}-s$, waarbij $e$ groot is en $r$ en $|s|$ relatief klein zijn. Fermatgetallen hebben bijvoorbeeld deze vorm. De wiskundigen Joe Buhler en Carl Pomerance bedachten later een manier om de speciale getallenlichamenzeef zo aan te passen, dat deze voor vrijwel alle samengestelde getallen kan worden gebruikt, met uitzondering van machten van priemgetallen. Dit leidde tot de algemene getallenlichamenzeef, meestal kortweg getallenlichamenzeef genoemd.

De eerste getallen die met de speciale getallenlichamenzeef werden gefactoriseerd, waren $2^{128}+1$, $\ 2^{144}-3$ (44 cijfers, ontbinding duurde destijds 47 uur) en $2^{153}+3$ (47 cijfers, ontbinding in 61 uur). Met deze methode is het later ook gelukt om onder andere het negende fermatgetal (155 cijfers) en enkele mersennepriemgetallen te ontbinden.

Een belangrijke uitdaging voor de getallenlichamenzeef is de ontbinding van RSA-getallen: producten van twee grote priemgetallen die worden gebruikt in de RSA-cryptografie. Een reeks van dergelijke getallen, aangeduid als RSA-$n$, is openbaar gemaakt. Hierbij geeft $n$ de bitlengte van het product aan. De priemfactoren van deze RSA-getallen zijn niet bekendgemaakt en werden niet bewaard.

De volgende twee factorisaties geven een beeld van de progressie in de toepassing van de getallenlichamenzeef. Een groep wiskundigen heeft RSA-768 (768 bits, 232 decimale cijfers) in december 2009 met behulp van de getallenlichamenzeef ontbonden en RSA-829 (829 bits, 250 decimale cijfers) is in 2020 ontbonden.

Idee

De getallenlichamenzeef is in zekere zin 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 ontbinden getal is.

Een verschil met de kwadratische zeef is dat niet langer uitsluitend met kwadratische veeltermen wordt gewerkt. 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.

Werking

De kwadratische zeef, waar de getallenlichamenzeef op is gebaseerd, zoekt naar getallen $x$ en $y$ zodanig dat

$x^{2}\equiv y^{2}{\pmod {N}}\quad$ en $\quad 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.

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$ 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 factoren gevonden die niet triviaal zijn. Op die factoren kunnen we, als ze zelf geen priemgetal 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

Ieder 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 dit 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 stelling 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

${\displaystyle \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 de 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}}.$

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, die uit uit een eindig aantal priemidealen bestaat van graad 1 van $\mathbb {Z} [\theta ]$, waarover de getallen $a+b\vartheta$ volledig in priemgetallen kunnen worden ontbonden en een rationale ontbindingsbasis $F$, die uit kleine priemgetallen bestaat, voor $\mathbb {Z}$ waarover de getallen $a+bm$ volledig in priemgetallen kunnen worden ontbonden. 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 van de paren $(a,b)$ of van een deel daarvan zodat

$\prod _{(a,b)\in U}(a+b\vartheta )=\beta ^{2}\quad$ 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$ 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{\bmod {p}}$

Daaruit volgt dat

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

ofwel dat $a$ van de vorm $a=-bm+kp$ met $k\in \mathbb {Z}$ moet zijn. Op deze manier kunnen we net zoals bij de zeef van Eratosthenes al veel $a$ als ongeschikt wegstrepen.

Opmerkingen

Het enige dat nu nog moet gebeuren 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 noch 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 ook voor keuzes die niet optimaal zijn, dus is dit 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 complexiteitsgraad van het algoritme wordt in de grote-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.

Voetnoten