Gebruiker:Tomenfre/Concept Getallenlichamenzeef

De getallenlichamenzeef is een methode 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 bewerken

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

Idee bewerken

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.^[4]

Achterliggende wiskunde bewerken

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 ϕ 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 ϕ $(x_{i})$ . Feitelijk vervult de functie ϕ hier de rol van een ringhomomorfisme, dat kwadraten in de ring $\mathbb {Z}$ afbeeldt op kwadraten in de ring $\mathbb {Z} /N\mathbb {Z} .$ De getallenlichamenzeef gaat uit van hetzelfde idee, maar algemener, door een andere ring dan $\mathbb {Z}$ te gebruiken.^[5]

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 bewerken

Een over de rationale getallen irreducibele veelterm (in $x$ ) heet monisch als de coëfficiënt voor de hoogste graad van $x$ gelijk is aan 1. Een monische, irreducibele veelterm $f$ van graad $d$ die alleen rationale coëfficiënten heeft, is over de complexe getallen volledig te ontbinden in lineaire factoren en dus te schrijven als

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

waar $\theta _{i}\in \mathbb {C}$ $\forall i\in \{1,\ldots ,d\}.$

Men kan nu een nulpunt $\theta$ van deze veelterm kiezen en de lichaamsuitbreiding $\mathbb {Q} (\theta )$ bekijken. Deze lichaamsuitbreiding is een lichaam, en kan worden gezien als de verzameling van veeltermen in $\theta$ met rationale coëfficiënten, ofwel de $\mathbb {Q}$ -lineaire combinaties van $\{1,\theta ,\theta ^{2},\ldots ,\theta ^{d-1}\}$ . Het zou prettig zijn als we ons konden beperken tot gehele coëfficiënten, dus $\mathbb {Z}$ -lineaire combinaties, omdat 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 monische veelterm met gehele coëfficiënten. Bij een gegeven monische, irreducibele veelterm $f(x)$ van graad $d$ met rationale coëfficiënten en een nulpunt $\theta \in \mathbb {C}$ kunnen we de verzameling $R[\theta ]$ vormen van alle algebraïsch gehele getallen in $\mathbb {Q} (\theta ).$ Deze verzameling vormt een deelring van het lichaam $\mathbb {Q} (\theta )$ . De verzameling van alle $\mathbb {Z}$ -lineaire combinaties van $\{1,\theta ,\theta ^{2},\ldots ,\theta ^{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^[4] zegt namelijk het volgende. Zij $f(x)$ een monische, irreducibele veelterm die alleen gehele coëfficiënten heeft, $\theta \in \mathbb {C}$ een nulpunt van deze veelterm en $m\in \mathbb {Z} /N\mathbb {Z}$ zodanig dat

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

Dan is de afbeelding

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

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

Als we zo'n $f$ , $\theta$ en $m$ hebben, dan kunnen we dus een surjectief ringhomomorfisme ϕ 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\theta )=\beta ^{2}

en

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

waar $\beta \in \mathbb {Z} [\theta ]$ 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\theta )\right)\equiv \prod _{(a,b)\in U}\phi (a+b\theta )\equiv \prod _{(a,b)\in U}(a+bm)\equiv y^{2}{\pmod {N}}.

^[4]

Het vinden van $U$ bewerken

Met de bovenstaande paragraaf in het achterhoofd zien we direct dat we een functie $f$ moeten kiezen. Daarbij zoeken we dan een nulpunt $\theta$ 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} [\theta ]$ te kiezen (bestaande uit een eindig aantal priemidealen van graad 1 van $\mathbb {Z} [\theta ]$ ) waarover de getallen $a+b\theta$ 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\theta$ 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\theta )=\beta ^{2}\quad {\textrm {en}}\quad \prod _{(a,b)\in U}(a+bm)=y^{2},

waar $\beta \in \mathbb {Z} [\theta ]$ 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 bewerken

Al wat nog rest, is het kiezen van een functie $f$ , een bijbehorend nulpunt $\theta$ 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.^[4]

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

N=m^{d}+a_{d-1}m^{d-1}+\cdots +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}+\cdots +a_{1}x+a_{0}.

Merk op dat $f$ niet irreducibel hoeft te zijn. Als $f$ reducibel is, dan 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 bewerken

De complexiteit van het algoritme wordt in de O-notatie gegeven door

O\left(\mathrm {e} ^{c\,(\log {n})^{1/3}(\log {\log {n}})^{2/3}}\right)\!,

waar $c$ een constante is met als waarde ongeveer $c\approx 1,923$ . Als grondtal voor de logaritme wordt e, het grondtal van de natuurlijke logaritme, gebruikt.

Ter vergelijking: de kwadratische zeef heeft als complexiteit

O\left(\mathrm {e} ^{(\log {n})^{1/2}(\log {\log {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

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

[1] H.W. Lenstra Jr., Het ontbinden van grote getallen in priemfactoren, Nieuwe Wiskrant 15, september 1995, 7-15

[2] A.K. Lenstra en H.W. Lenstra Jr., The development of the number field sieve, Lecture notes in mathematics, Springer-Verlag, Berlijn, 1993

[3] T. Kleinjung et al., Factorization of a 768-bit RSA modulus

[brig98-4] M.E. Briggs, An Introduction to the General Number Field Sieve, masterscriptie, april 1998

[5] 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.

[1]

[2]

[3]

[4]

[5]