Kwadratische zeef

De kwadratische zeef is een algoritme om samengestelde getallen te ontbinden in priemfactoren. Deze methode is gebaseerd op Dixons factorisatiemethode en is in 1984 ontwikkeld door de Amerikaanse wiskundige Carl Pomerance. De kwadratische zeef is in 1994 gebruikt om RSA-129 te kraken. Het is een van de snelste algoritmen om een getal in factoren te ontbinden. De getallenlichamenzeef is een stuk ingewikkelder dan de kwadratische zeef, maar sneller voor getallen groter dan 130 cijfers. De tijd die de kwadratische zeef en de getallenlichamenzeef nodig hebben om getallen tussen de 100 en 130 cijfers te ontbinden, is sterk afhankelijk van de implementatie van het algoritme en de beschikbare opslagruimte. Pomerance schrijft dat de kwadratische zeef sneller is voor getallen tot 100 cijfers.

Grondgedachte

Het achterliggende idee van de kwadratische zeef is modulair rekenen en berust op de voorstelling van een getal $N$ als verschil van twee kwadraten:

$x^{2}-y^{2}=(x+y)\cdot (x-y)=N$

Daarmee zijn twee delers $x+y$ en $x-y$ van $N$ gevonden.

Om een samengesteld getal $N$ te ontbinden in priemfactoren, gaat men op zoek naar twee verschillende getallen $x$ en $y\neq \pm x$ zodanig dat

$x^{2}\equiv y^{2}{\pmod {N}}$

In dat geval geldt namelijk 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 beide niet gelijk zijn aan 1, zijn er twee factoren gevonden, die geen 1 of $N$ zijn. Op die factoren kan, als ze niet al allebei zelf een priemgetal zijn, hetzelfde procedé worden toegepast om een priemfactorontbinding van $N$ te verkrijgen.

Bovenstaand idee is de basis van veel methoden om getallen te ontbinden, zoals behalve de kwadratische zeef ook Fermats factorisatiemethode, Dixons factorisatiemethode en de getallenlichamenzeef. Je zou natuurlijk ook alle $x$ en $y$ af kunnen gaan om twee factoren te vinden, maar de kwadratische zeef is in het algemeen veel sneller. De kwadratische zeef verschilt namelijk van de andere methoden door de wijze, waarop zulke getallen $x$ en $y$ gevonden worden. Merk op dat het zou kunnen dat de kwadratische zeef ons getallen $x$, $y$ geeft die ons geen priemfactoren van $N$ opleveren, omdat het niet is uitgesloten dat een van de gemene delers $\mathrm {ggd} (N,x-y)$ en $\mathrm {ggd} (N,x+y)$ gelijk is aan 1 (waarmee de andere precies $N$ is). De kans hierop is echter klein als $N$ veel delers heeft. Bovendien kunnen we de kwadratische zeef opnieuw gebruiken om andere getallen $x$, $y$ te vinden.

Achterliggende wiskunde

Om het samengestelde getal $N$ te ontbinden in priemfactoren, definieert men met de entierfunctie $m_{N}=\lfloor {\sqrt {N\ }}\rfloor$

de functie

$f(x)=(x+m_{N})^{2}-N$

Dan zoekt men een rij getallen $x_{1},x_{2},\ldots$ zodanig dat $f(x_{1})\cdot f(x_{2})\cdot \ldots \cdot f(x_{k})$ een kwadraat is modulo $N$. Als dat zo is, kan deze uitdrukking als definitie voor $y^{2}$ worden genomen, omdat

$((x_{1}+m)^{2}-N)\cdot ((x_{2}+m)^{2}-N)\cdot \ldots \cdot ((x_{k}+m)^{2}-N)\equiv ((x_{1}+m)\cdot (x_{2}+m)\cdots (x_{k}+m))^{2}{\pmod {N}}$

al een kwadraat is.

We weten dat een getal een kwadraat is als iedere priemfactor in zijn ontbinding een even aantal keer voorkomt. Om te controleren of zo’n product van factoren $f(x_{i})$ een kwadraat is, kijken we naar de priemfactorontbindingen. Om de berekeningen eenvoudig te houden hebben we het liefst kleine priemgetallen in de ontbindingen. Om die reden definiëren we een zogeheten ontbindingsbasis en beschouwen we alleen getallen die volledig te ontbinden zijn in elementen uit deze basis, zogeheten gladde getallen. De ontbindingsbasis is gedefinieerd als

$F(B):=\{p:p{\mbox{ priem}}\mid p\leq B\}\cup \{-1\}$

voor positieve gehele getallen $B$.

Kies nu een grenswaarde $M$ en beschouw alle gehele getallen in het interval $[-M,M]$. Uit dit interval zullen de getallen $x_{i}$ afkomstig zijn. Uit de bovenstaande definitie van de functie $f$ volgt dat $f(x_{i})\approx 2x_{i}\lfloor {\sqrt {N}}\rfloor$. Hieraan zien we direct een van de grote voordelen van de kwadratische zeef en het gebruik van de voorgenoemde functie: de residuen $f(x_{i})$ modulo $N$ zijn veel kleiner dan willekeurige kwadraten modulo $N$, wat betekent dat de kans dat ze volledig te ontbinden zijn in kleine priemgetallen, dus getallen uit $F(B)$, groot is.

Maak nu een lijst van alle getallen $x_{1},x_{2},\ldots$ uit het interval $[-M,M]$ voor welke de bijbehorende $f(x_{1}),f(x_{2}),\ldots$ inderdaad volledig te ontbinden zijn in getallen uit de gekozen ontbindingsbasis.

Voor iedere functiewaarde $f(x_{i})$ kunnen we nu, net als bij Dixons factorisatiemethode, een vector maken, geïndiceerd door de elementen van onze ontbindingsbasis $F(B)$. We noteren in deze vector voor ieder element uit de ontbindingsbasis hoe vaak dit getal modulo 2 voorkomt in de priemfactorontbinding van $f(x_{i})$. Ter illustratie: zou onze ontbindingsbasis $F(7)$ zijn en de functiewaarde 60, dan wordt de bijbehorende vector $(1,0,1,1,0)$, want $60=1\cdot 2^{2}\cdot 3\cdot 5$. We zien dat de factoren −1, 3 en 5 een oneven aantal keren voorkomen en 2 en 7 een even aantal keren. Zo hoort bij iedere $x_{i}$ een vector.

Merk op dat het vermenigvuldigen van twee getallen $x_{i}$ en $x_{j}$ leidt tot het optellen van de bijbehorende vectoren modulo 2. Omdat in een kwadraat alle priemfactoren een even aantal keer voorkomen, zoeken we nu een optelling van verschillende vectoren die de nulvector modulo 2 vormen. Dit kan onder andere met lineaire algebra. Door alle vectoren onder elkaar te zetten, krijgen we een binaire matrix. Het probleem wordt dan te zoeken naar een combinatie van rijen die opgeteld de nulvector opleveren.

Als we uiteindelijk een afhankelijkheid gevonden hebben, dan definiëren we $x$ als het product van de corresponderende $(x_{i}+m)$'s. We definiëren $y$ als de vierkantswortel van het product van de bijbehorende $f(x_{i})$'s. Nu is $\mathrm {ggd} (N,x-y)$ hopelijk een niet-triviale factor. Uitdelen geeft dan nog een niet-triviale factor. Mocht dit niet zo te zijn, probeer dan een andere combinatie van $x_{i}$'s te vinden of kies een grotere $B$ en/of $M$. Mochten de niet-triviale factoren niet priem zijn, dan kan eventueel opnieuw de kwadratische zeef worden toegepast op deze factoren om zo tot een priemfactorontbinding te komen.

Een vraag die zich direct opwerpt, is wat de beste keuze voor $B$ en $M$ is. Zoals gezegd willen we graag kleine priemgetallen in onze ontbindingsbasis, wat neerkomt op $B$ klein kiezen, maar dan zullen we in het algemeen een grote waarde voor $M$ moeten nemen om voldoende verschillende getallen te vinden die volledig factoriseren over de gekozen ontbindingsbasis. Anderzijds zal bij een grote waarde van $B$ een kleine waarde van $M$ voldoen, omdat er dan veel getallen zijn die volledig factoriseren. De Amerikaanse wiskundige Richard Schroeppel heeft al aan het einde van de jaren 1970 over dit probleem nagedacht, omdat het ook optrad in andere methoden om getallen te ontbinden. Pomerance behandelt al in zijn artikel uit 1984 enkele resultaten hierover.

Aanvullende opmerkingen

De functie $f$ zoals hierboven gedefinieerd is niet de enige die werkt. Eventueel kunnen we ook

$f(x)=(x+m+1)^{2}-N$

gebruiken, wat door sommige auteurs impliciet gedaan wordt; zij definiëren $m$ als

$m=\lfloor {\sqrt {N}}\rfloor +1$

Dat dit ook werkt, blijkt uit het tweede voorbeeld hieronder.

Feitelijk voldoen veel veeltermen van de vorm

$f(x)=(Ax+B)^{2}-N,\quad {\text{ met}}\ A,B\in \mathbb {Z}$

In de praktijk kiest men $A$ en $B$ zodanig dat $B^{2}-N$ een veelvoud is van $A$, zeg $B^{2}-N=AC$ ofwel

$B^{2}\equiv N{\pmod {A}}$

De veelterm is dan te herschrijven als

$f(x)=A(Ax^{2}+2Bx+C)$

Als $A$ een kwadraat is, dan hoeven we alleen nog te zorgen dat de factor $Ax^{2}+2Bx+C$ een kwadraat is om te bereiken dat $f(x)$ een kwadraat is. Door $A$ te kiezen als het kwadraat van een priemgetal, bereikt men dat de vergelijking $B^{2}\equiv N{\pmod {A}}$ precies twee oplossingen heeft, wat het rekenwerk verder vergemakkelijkt.

Door verschillende veeltermen van bovenstaande vorm te gebruiken, kan het rekenwerk over een aantal computers worden verdeeld. Elke computer krijgt dan zijn eigen veelterm toegewezen. Omdat er geen onderlinge communicatie tussen de computers hoeft plaats te vinden totdat al het rekenwerk gedaan is, is deze aanpak erg geschikt voor omvangrijk rekenwerk. Deze methode staat in het Engels wel bekend als de multiple polynomial quadratic sieve (MPQS). Het kraken van RSA-129 gebeurde ook met deze methode.

Verder hoeven we in de ontbindingsbasis alleen getallen $p$ op te nemen waarvoor geldt dat $N$ een kwadratisch residu modulo $p$ is. Als een priemgetal $p\in F(B)$ voorkomt in de ontbinding van een getal $f(x)$ met $x\in [-M,M]$, dan geldt immers dat

$p\mid (x-m)^{2}-N$,

waaruit direct volgt dat

$(x-m)^{2}=N{\pmod {p}}$

Anders gezegd: als voor een priemgetal $p$ geldt dat $N$ geen kwadratisch residu modulo $p$ is, dan zal dit getal nooit optreden als factor in de ontbinding van getallen $f(x_{i})$.

Het woord zeef in de naam kwadratische zeef heeft betrekking op de wijze waarop gecontroleerd wordt of de getallen $f(x_{i})$ glad zijn. Dit wordt het best duidelijk door een vergelijking met de zeef van Eratosthenes, die gebruikt kan worden om te bepalen welke gehele getallen een priemgetal zijn. Bij die methode streept men van klein naar groot een voor een alle veelvouden van een getal weg, waarna het eerstvolgende overgebleven getal wel priem moet zijn. Bij de kwadratische zeef neemt men een $f(x_{i})$ en deelt men alle elementen uit de ontbindingsbasis uit. Als na dit procedé het overgebleven getal niet 1 is, dan is $f(x_{i})$ geen glad getal.

Een voorbeeld hierbij is het volgende. Stel dat $f(x)=-90$ voor zekere $x$ en de ontbindingsbasis $F(3)=\{-1,2,3\}$ is. Omdat $f(x)$ een negatief getal is, delen we een factor −1 uit, waarna we 90 overhouden. Na uitdelen van de factor 2 houden we 45 over. Dat is deelbaar door twee factoren 3, waarna we 5 overhouden. Alle getallen uit de ontbindingsbasis zijn aan bod gekomen en het resultaat is niet 1, dus is $f(x)$ geen glad getal.

Voorbeelden

Eenvoudig voorbeeld

Stel dat we de priemfactorontbinding van het getal 3937 willen weten. Dit getal is samengesteld, dus kunnen we de kwadratische zeef gebruiken om de priemfactorontbinding te vinden. We volgen nu de methode die is uitgelegd in bovenstaande paragraaf.

Omdat $62^{2}<3937$ en $63^{2}>3937$ geldt dat de entier van ${\sqrt {3937\ }}$ gelijk is aan $\lfloor {\sqrt {3937\ }}\rfloor =62$. We definiëren nu de veelterm $f(x)=(x+62)^{2}-3937$. We definiëren verder $B=3$ en $M=3$. Dan krijgen we $x_{i}\in [-3,3]$ en

$F(3)=\{p:p{\mbox{ priem}}\mid p\leq 3\}\cup \{-1\}=\{-1,2,3\}$

Dit levert op:

Tabel met waarden $f(x_{i})$ en priemfactorontbinding
$f(-3)$	$=-456$	$=-1$ $\cdot$ $2^{3}$ $\cdot$ $3$ $\cdot$ $19$
$f(-2)$	$=-337$	$=-1$ $\cdot$ $337$
$f(-1)$	$=-216$	$=-1$ $\cdot$ $2^{3}$ $\cdot$ $3^{3}$	alleen getallen uit $F(3)$
$f(0)$	$=-93$	$=-1$ $\cdot$ $3$ $\cdot$ $31$
$f(1)$	$=32$	$=2^{5}$	alleen getallen uit $F(3)$
$f(2)$	$=159$	$=3$ $\cdot$ $53$
$f(3)$	$=288$	$=2^{5}$ $\cdot$ $3^{2}$	alleen getallen uit $F(3)$

De vraag is nu: kunnen we een rij $x_{1},\ldots ,x_{k}$ vinden zodanig dat de priemfactorontbinding van $f(x_{i})$ alleen getallen uit $F(3)$ bevat en zodanig dat het product van de $f(x_{i})$ een kwadraat is? In dit eenvoudige voorbeeld is direct te zien dat dit kan: neem $x_{1}=1$ en $x_{2}=3$, dan bestaat de priemfactorontbinding van $f(1)$ en $f(3)$ alleen uit priemgetallen in $F(3)$. Bovendien geldt

$f(1)\cdot f(3)=2^{5}\cdot 2^{5}\cdot 3^{2}=2^{10}\cdot 3^{2}=(2^{5}\cdot 3)^{2}$

We nemen dus

$y={\sqrt {f(1)\cdot f(3)}}={\sqrt {(2^{5}\cdot 3)^{2}}}=2^{5}\cdot 3\equiv 96{\pmod {3937}}$

Merk op dat ook geldt

$f(1)=(1+62)^{2}-3937=63^{2}-3937\equiv 63^{2}{\pmod {3937}}$

en evenzo

$f(3)\equiv 65^{2}{\pmod {3937}}$

Als we nemen

$x=63\cdot 65\equiv 158{\pmod {3937}}$,

geldt

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

De laatste stap zegt nu:

$3937=\mathrm {ggd} (3937,\ x^{2}-y^{2})$

${\color {White}3937}=\mathrm {ggd} (3937,\ x-y)\cdot \mathrm {ggd} (3937,\ x+y)$

${\color {White}3937}=\mathrm {ggd} (3937,\ 62)\cdot \mathrm {ggd} (3937,\ 254)$

${\color {White}3937}=31\cdot 127$

We hebben nu de priemfactorontbinding van 3937 gevonden, aangezien 31 en 127 beide zelf priem zijn.

Uitgebreid voorbeeld

In dit voorbeeld zullen we aantonen dat ook de functie

$f(x)=(x+m+1)^{2}-N$

gebruikt kan worden.

Stel dat we de priemfactorontbinding van het getal 45 willen weten. Omdat ${\sqrt {45}}\approx 6,71$ volgt $m=6$ en $m+1=7$. De functie wordt dus $f(x)=(x+7)^{2}-45$.

Voor dit voorbeeld kiezen we $M=5$ en $B=11$. Merk op dat deze waarde van $B$ groter is dan in de praktijk gebruikt zou worden. Voor het voorbeeld is het echter instructief deze waarde te nemen; in de praktijk zou men sowieso niet zulke kleine getallen ontbinden met de kwadratische zeef.

Alles tezamen volgt dat nu $x_{i}\in [-5,5]$ en $F(11)=\{-1,2,3,5,7,11\}$.

Dit levert op:

Tabel met waarden $f(x_{i})$ en priemfactorontbinding
$f(-5)$	$=-44$	$=-1$ $\cdot$ $2^{2}$ $\cdot$ $11$	alleen getallen uit $F(11)$
$f(-4)$	$=-36$	$=-1$ $\cdot$ $2^{2}$ $\cdot$ $3^{2}$	alleen getallen uit $F(11)$
$f(-3)$	$=-29$	$=29$
$f(-2)$	$=-20$	$=-1$ $\cdot$ $2^{2}$ $\cdot$ $5$	alleen getallen uit $F(11)$
$f(-1)$	$=-9$	$=-1$ $\cdot$ $3^{2}$	alleen getallen uit $F(11)$
$f(0)$	$=4$	$=2^{2}$	alleen getallen uit $F(11)$
$f(1)$	$=19$	$=19$
$f(2)$	$=36$	$=2^{2}$ $\cdot$ $3^{2}$	alleen getallen uit $F(11)$
$f(3)$	$=55$	$=5$ $\cdot$ $11$	alleen getallen uit $F(11)$
$f(4)$	$=76$	$=2^{2}$ $\cdot$ $19$
$f(5)$	$=99$	$=3^{2}$ $\cdot$ $11$	alleen getallen uit $F(11)$

Omdat het bij grotere aantallen functiewaarden moeilijk is een afhankelijkheid direct te zien, zullen we een binaire matrix opstellen en daarin zoeken naar afhankelijke rijen. Zoals eerder beschreven nemen we in deze matrix de vectoren op met daarin de machten van de priemgetallen modulo 2 van alle functiewaarden die volledig ontbinden over $F(11)$.

Dit levert de volgende matrix op:

${\begin{pmatrix}1&2&0&0&0&1\\1&2&2&0&0&0\\1&2&0&1&0&0\\1&0&2&0&0&0\\0&2&0&0&0&0\\0&2&2&0&0&0\\0&0&0&1&0&1\\0&0&2&0&0&1\\\end{pmatrix}}\equiv {\begin{pmatrix}1&0&0&0&0&1\\1&0&0&0&0&0\\1&0&0&1&0&0\\1&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&1&0&1\\0&0&0&0&0&1\\\end{pmatrix}}{\pmod {2}}$

Ter verduidelijking: in gedachten denk je boven de linker matrix de rij −1, 2, 3, 5, 7, 11 en links van de matrix de kolom −5, −4, −2, −1, 0, 2, 3, 5 (alle $x_{i}$ horend bij de $f(x_{i})$ die volledig ontbinden over de gekozen ontbindingsbasis). Dan staat in iedere rij in de $j$-de kolom hoe vaak de factor boven die kolom in de ontbinding van de betreffende functiewaarde voorkomt. De rechter matrix reduceert elk element modulo 2. Na enig denkwerk zien we dat het optellen van de eerste, tweede, derde, vierde en zevende rij van de rechter matrix de nulvector oplevert. Bij die rijen horen de $x_{i}$-waarden −5, −4, −2, −1 en 3. We definiëren daarom

$x=(7-5)\cdot (7-4)\cdot (7-2)\cdot (7-1)\cdot (7+3)$

${\color {White}x}=2\cdot 3\cdot 5\cdot 6\cdot 10$

${\color {White}x}=1800$

${\color {White}x}\equiv 45{\pmod {45}}$

Vervolgens definiëren we $y$ als

$y={\sqrt {f(-5)\cdot f(-4)\cdot f(-2)\cdot f(-1)\cdot f(3)}}$

${\color {White}y}={\sqrt {-1\cdot 2^{2}\cdot 11\cdots 3^{2}\cdot 11}}$

${\color {White}y}\equiv 45{\pmod {45}}$

Er geldt nu dat $\mathrm {ggd} (x,y)=\mathrm {ggd} (45,45)=45$, dus we hebben helaas een triviale deler gevonden.

Uit de rechter matrix volgt echter ook dat de eerste, tweede en laatste rij opgeteld de nulvector vormen. In dat geval blijkt $x\equiv 45$ en $y\equiv 18$ te zijn, waaruit volgt dat $\mathrm {ggd} (45,18)=9$ een deler van 45 is. We hebben nu een niet-triviale deler van 45 gevonden en na uitdelen volgt direct de priemfactorontbinding van 45.

Beknopt voorbeeld

Voor $N=6501,\ B=13,\ M=20$ en $f(x)=(x+81)^{2}-6501$ krijgen we de volgende tabel (de niet-gladde functiewaarden zijn weggelaten):

Tabel met waarden $f(x_{i})$ en priemfactorontbinding
$f(-15)$	$=-2145$	$=-1$ $\cdot$ $3$ $\cdot$ $5$ $\cdot$ $11$ $\cdot$ $13$	alleen getallen uit $F(13)$
$f(-4)$	$=-572$	$=-1$ $\cdot$ $2^{2}$ $\cdot$ $11$ $\cdot$ $13$	alleen getallen uit $F(13)$
$f(-2)$	$=-260$	$=-1$$\cdot$ $2^{2}$$\cdot$ $5$$\cdot$ $13$	alleen getallen uit $F(13)$
$f(0)$	$=60$	$=2^{2}$ $\cdot$ $3$ $\cdot$ $5$	alleen getallen uit $F(13)$
$f(18)$	$=3300$	$=2^{2}$ $\cdot$ $3$$\cdot$ $5^{2}$$\cdot$ $11$	alleen getallen uit $F(13)$

Hierbij hoort de volgende binaire matrix:

${\begin{pmatrix}1&0&1&1&0&1&1\\1&0&0&0&0&1&1\\1&0&0&1&0&0&1\\0&0&1&1&0&0&0\\0&0&1&0&0&1&0\\\end{pmatrix}}$

De tweede tot en met vijfde rij tellen op tot de nulvector, wat leidt tot

$x=(81-4)\cdot (81-2)\cdot (81+0)\cdot (81+18)$

${\color {White}x}=77\cdot 79\cdot 81\cdot 99$

${\color {White}x}\equiv 2574{\pmod {6501}}$

Na enig rekenwerk volgt $y\equiv 4323{\pmod {6501}}$, waaruit volgt $\mathrm {ggd} (2574,4323)=33$. Dit is geen triviale deler en door uitdelen vinden we snel dat

$6501=33\cdot 197=3\cdot 11\cdot 197$

Complexiteit

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

$O\left(e^{\sqrt {\log {n}\log {\log {n}}}}\right)$

Als grondtal voor de logaritme wordt e, het grondtal van de natuurlijke logaritme, gebruikt.

De bovenstaande uitdrukking kan worden herschreven tot

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

een vorm waarin het verschil met de getallenlichamenzeef goed tot uiting komt. Dat algoritme heeft namelijk als complexiteit

$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$. Hieruit volgt direct dat voor grote $n$ men beter de getallenlichamenzeef kan gebruiken om een getal te ontbinden.

Voetnoten