Kwadratische zeef

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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. Momenteel is de kwadratische zeef een van de snelste algoritmen om een getal te factoriseren. 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 getallenlichamzeef 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.[1]

Idee[bewerken]

Het achterliggende idee van de kwadratische zeef berust op modulair rekenen en is het volgende.[2] Als we een samengesteld getal N willen ontbinden in priemfactoren, dan gaan we op zoek naar twee verschillende getallen x, y\ne \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, dan hebben we twee niet-triviale factoren, dat wil zeggen niet 1 en niet N, gevonden. Op die factoren kunnen we, als ze niet al allebei zelf priem zijn, hetzelfde procedé toepassen om een priemfactorontbinding van N te verkrijgen.

Bovenstaand idee is de basis van veel methoden om getallen te ontbinden, zoals (naast de kwadratische zeef) 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[bewerken]

Stel dat we het samengestelde getal N willen ontbinden in priemfactoren. We bepalen dan allereerst met de entierfunctie m := \lfloor \sqrt{N}\rfloor en definiëren de functie

f(x)\,\!=(x+m)^2-N.

Nu zoeken we een rij getallen x_1, x_2, \ldots zodanig dat f(x_1)\cdot f(x_2)\cdots f(x_k) een kwadraat is modulo N. Als dat zo is, dan kunnen we deze uitdrukking als definitie voor y^2 nemen omdat ((x_1+m)^2-N)\cdot ((x_2+m)^2-N)\cdots ((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 formeel 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 eind jaren 1970 over dit probleem nagedacht, omdat het ook optrad in andere factorisatiemethoden. Pomerance behandelt al in zijn artikel uit 1984 enkele resultaten hierover.[2]

Aanvullende opmerkingen[bewerken]

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\textrm{ 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 meerdere veeltermen van bovenstaande vorm te gebruiken, kan het rekenwerk verdeeld worden over meerdere computers. 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).[3] Het kraken van RSA-129 gebeurde ook met deze methode.[4]

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[bewerken]

Eenvoudig voorbeeld[bewerken]

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},

dan 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[bewerken]

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[bewerken]

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[bewerken]

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

O\left(\mathrm{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.

Bronnen, noten en/of referenties
  1. C. Pomerance, A tale of two sieves, Notices of the American Mathematical Society. 43 (1996), 1473-1485.
  2. a b C. Pomerance, The quadratic sieve factoring algorithm, Advances in Cryptology, Proceedings of Eurocrypt 84, Paris, 1984, T. Beth. N. Cot, and I. Ingemarsson, eds., Lecture Notes in Computer Sci. 209 (1985), 169-182.
  3. E. Landquist, The Quadratic Sieve Factoring Algorithm, MATH 488: Cryptographic Algorithms, 14 december 2001
  4. D. Atkins, M. Graff, A.K. Lenstra, P.C. Leyland, The magic words are squeamish ossifrage