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.[1]
Grondgedachte
Het achterliggende idee van de kwadratische zeef is modulair rekenen[2] en berust op de voorstelling van een getal
als verschil van twee kwadraten:
![{\displaystyle x^{2}-y^{2}=(x+y)\cdot (x-y)=N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a9235793f1b3d028bb7c2d48dc7e3a395fb1406)
Daarmee zijn twee delers
en
van
gevonden.
Om een samengesteld getal
te ontbinden in priemfactoren, gaat men op zoek naar twee verschillende getallen
en
zodanig dat
![{\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11af429b925c7fe1c3918d7ce41bff71e19b5495)
In dat geval geldt namelijk dat
,
waaruit direct volgt
![{\displaystyle N=\mathrm {ggd} (N,\ x^{2}-y^{2})=\mathrm {ggd} (N,\ x-y)\cdot \mathrm {ggd} (N,\ x+y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c544ed640da998b5cdf1b51f801c43f5d72d52f8)
Als deze grootste gemene delers beide niet gelijk zijn aan 1, zijn er twee factoren gevonden, die geen 1 of
zijn. Op die factoren kan, als ze niet al allebei zelf een priemgetal zijn, hetzelfde procedé worden toegepast om een priemfactorontbinding van
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
en
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
en
gevonden worden. Merk op dat het zou kunnen dat de kwadratische zeef ons getallen
,
geeft die ons geen priemfactoren van
opleveren, omdat het niet is uitgesloten dat een van de gemene delers
en
gelijk is aan 1 (waarmee de andere precies
is). De kans hierop is echter klein als
veel delers heeft. Bovendien kunnen we de kwadratische zeef opnieuw gebruiken om andere getallen
,
te vinden.
Achterliggende wiskunde
Om het samengestelde getal
te ontbinden in priemfactoren, definieert men met de entierfunctie
de functie
![{\displaystyle f(x)=(x+m_{N})^{2}-N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/091ab286fc1dbebee78160c2f8d7aa2c7c0d5f10)
Dan zoekt men een rij getallen
zodanig dat
een kwadraat is modulo
. Als dat zo is, kan deze uitdrukking als definitie voor
worden genomen, omdat
![{\displaystyle ((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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/01679299f02c33ccac9ebf7676c24296ade6bb2e)
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
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
![{\displaystyle F(B):=\{p:p{\mbox{ priem}}\mid p\leq B\}\cup \{-1\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e7221b7930b4756cf9d5c2067957ac9248c5a18)
voor positieve gehele getallen
.
Kies nu een grenswaarde
en beschouw alle gehele getallen in het interval
. Uit dit interval zullen de getallen
afkomstig zijn. Uit de bovenstaande definitie van de functie
volgt dat
. Hieraan zien we direct een van de grote voordelen van de kwadratische zeef en het gebruik van de voorgenoemde functie: de residuen
modulo
zijn veel kleiner dan willekeurige kwadraten modulo
, wat betekent dat de kans dat ze volledig te ontbinden zijn in kleine priemgetallen, dus getallen uit
, groot is.
Maak nu een lijst van alle getallen
uit het interval
voor welke de bijbehorende
inderdaad volledig te ontbinden zijn in getallen uit de gekozen ontbindingsbasis.
Voor iedere functiewaarde
kunnen we nu, net als bij Dixons factorisatiemethode, een vector maken, geïndiceerd door de elementen van onze ontbindingsbasis
. We noteren in deze vector voor ieder element uit de ontbindingsbasis hoe vaak dit getal modulo 2 voorkomt in de priemfactorontbinding van
. Ter illustratie: zou onze ontbindingsbasis
zijn en de functiewaarde 60, dan wordt de bijbehorende vector
, want
. 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
een vector.
Merk op dat het vermenigvuldigen van twee getallen
en
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
als het product van de corresponderende
's. We definiëren
als de vierkantswortel van het product van de bijbehorende
's. Nu is
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
's te vinden of kies een grotere
en/of
. 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
en
is. Zoals gezegd willen we graag kleine priemgetallen in onze ontbindingsbasis, wat neerkomt op
klein kiezen, maar dan zullen we in het algemeen een grote waarde voor
moeten nemen om voldoende verschillende getallen te vinden die volledig factoriseren over de gekozen ontbindingsbasis. Anderzijds zal bij een grote waarde van
een kleine waarde van
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.[2]
Aanvullende opmerkingen
De functie
zoals hierboven gedefinieerd is niet de enige die werkt. Eventueel kunnen we ook
![{\displaystyle f(x)=(x+m+1)^{2}-N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14e4818838c6fced7dca32ac651b420be18c1046)
gebruiken, wat door sommige auteurs impliciet gedaan wordt; zij definiëren
als
![{\displaystyle m=\lfloor {\sqrt {N}}\rfloor +1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9eb077cf16ecceaf679ebc79f70c81c94c955253)
Dat dit ook werkt, blijkt uit het tweede voorbeeld hieronder.
Feitelijk voldoen veel veeltermen van de vorm
![{\displaystyle f(x)=(Ax+B)^{2}-N,\quad {\text{ met}}\ A,B\in \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/41a04a3e675c68af21c03ddc432a35248033120d)
In de praktijk kiest men
en
zodanig dat
een veelvoud is van
, zeg
ofwel
![{\displaystyle B^{2}\equiv N{\pmod {A}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1856113c79b2a6f02054b571166e5342176c4540)
De veelterm is dan te herschrijven als
![{\displaystyle f(x)=A(Ax^{2}+2Bx+C)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f764f559629f5962a6be1418fb0c27d81657a5df)
Als
een kwadraat is, dan hoeven we alleen nog te zorgen dat de factor
een kwadraat is om te bereiken dat
een kwadraat is. Door
te kiezen als het kwadraat van een priemgetal, bereikt men dat de vergelijking
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).[3] Het kraken van RSA-129 gebeurde ook met deze methode.[4]
Verder hoeven we in de ontbindingsbasis alleen getallen
op te nemen waarvoor geldt dat
een kwadratisch residu modulo
is. Als een priemgetal
voorkomt in de ontbinding van een getal
met
, dan geldt immers dat
,
waaruit direct volgt dat
![{\displaystyle (x-m)^{2}=N{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0785b268f2c419a16d26ef4dd57872040a506691)
Anders gezegd: als voor een priemgetal
geldt dat
geen kwadratisch residu modulo
is, dan zal dit getal nooit optreden als factor in de ontbinding van getallen
.
Het woord zeef in de naam kwadratische zeef heeft betrekking op de wijze waarop gecontroleerd wordt of de getallen
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
en deelt men alle elementen uit de ontbindingsbasis uit. Als na dit procedé het overgebleven getal niet 1 is, dan is
geen glad getal.
Een voorbeeld hierbij is het volgende. Stel dat
voor zekere
en de ontbindingsbasis
is. Omdat
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
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
en
geldt dat de entier van
gelijk is aan
. We definiëren nu de veelterm
. We definiëren verder
en
. Dan krijgen we
en
![{\displaystyle F(3)=\{p:p{\mbox{ priem}}\mid p\leq 3\}\cup \{-1\}=\{-1,2,3\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a972ee242468859c6ed7c1ba217eaf0df6a0d580)
Dit levert op:
Tabel met waarden en priemfactorontbinding |
![{\displaystyle f(-3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8634279e6e0f5e769a01da592dbd301679723062) | | | |
![{\displaystyle f(-2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f85ab48a9bda8c96a794fe2ea54b28c736095df6) | | | |
![{\displaystyle f(-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/061fcbbd3a8299a1aabd60206e185c74c61d5862) | | | alleen getallen uit |
![{\displaystyle f(0)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc54adf96acf7e2466de00b7739144d36840108f) | | | |
![{\displaystyle f(1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/948f00426d32f835b4cefa1a56aebd8e18ba7d3c) | | | alleen getallen uit |
![{\displaystyle f(2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65f247dc5542263d64ef5f4346fc7cae009740f4) | | | |
![{\displaystyle f(3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bd9b5d7da173a2b3150a2196cb63d4fac80fe23) | | | alleen getallen uit |
De vraag is nu: kunnen we een rij
vinden zodanig dat de priemfactorontbinding van
alleen getallen uit
bevat en zodanig dat het product van de
een kwadraat is? In dit eenvoudige voorbeeld is direct te zien dat dit kan: neem
en
, dan bestaat de priemfactorontbinding van
en
alleen uit priemgetallen in
. Bovendien geldt
![{\displaystyle f(1)\cdot f(3)=2^{5}\cdot 2^{5}\cdot 3^{2}=2^{10}\cdot 3^{2}=(2^{5}\cdot 3)^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/58e8d1f979f92d54faf25390e64e05604fbfa50b)
We nemen dus
![{\displaystyle y={\sqrt {f(1)\cdot f(3)}}={\sqrt {(2^{5}\cdot 3)^{2}}}=2^{5}\cdot 3\equiv 96{\pmod {3937}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/08fe5d702d8e17f3a6820c07ea9c2b9e8ad92149)
Merk op dat ook geldt
![{\displaystyle f(1)=(1+62)^{2}-3937=63^{2}-3937\equiv 63^{2}{\pmod {3937}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75703d70d9350b4703cd966c728ddb24c7726c21)
en evenzo
![{\displaystyle f(3)\equiv 65^{2}{\pmod {3937}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1c5569c114dd0d2f039ecd730e8260eb25cbc6d)
Als we nemen
,
geldt
![{\displaystyle x^{2}\equiv y^{2}{\pmod {3937}}\quad {\mbox{ en }}x\neq \pm y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/734945190a6cf909bb0ccf70feb2137f8b98ae43)
De laatste stap zegt nu:
![{\displaystyle 3937=\mathrm {ggd} (3937,\ x^{2}-y^{2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/42dfcb252e390a539b5bb4e75ff19b0aa1e8f98d)
![{\displaystyle {\color {White}3937}=\mathrm {ggd} (3937,\ x-y)\cdot \mathrm {ggd} (3937,\ x+y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7705e8e1aa60bb1f602b7a188ca432b0991f62a)
![{\displaystyle {\color {White}3937}=\mathrm {ggd} (3937,\ 62)\cdot \mathrm {ggd} (3937,\ 254)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c07f5bd624768580c8e96ef7e8370782e5cd9a5)
![{\displaystyle {\color {White}3937}=31\cdot 127}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eaf0d506241f631c99fbde17b1a1a5a9cc24e9b5)
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
![{\displaystyle f(x)=(x+m+1)^{2}-N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14e4818838c6fced7dca32ac651b420be18c1046)
gebruikt kan worden.
Stel dat we de priemfactorontbinding van het getal 45 willen weten. Omdat
volgt
en
. De functie wordt dus
.
Voor dit voorbeeld kiezen we
en
. Merk op dat deze waarde van
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
en
.
Dit levert op:
Tabel met waarden en priemfactorontbinding |
![{\displaystyle f(-5)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb973a2b9cddc1ebb5aa58b4f08d971737f0c5d2) | | | alleen getallen uit |
![{\displaystyle f(-4)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb7aa168b07af0bf20c4ac8f6d6bf9412bdda685) | | | alleen getallen uit |
![{\displaystyle f(-3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8634279e6e0f5e769a01da592dbd301679723062) | | | |
![{\displaystyle f(-2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f85ab48a9bda8c96a794fe2ea54b28c736095df6) | | | alleen getallen uit |
![{\displaystyle f(-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/061fcbbd3a8299a1aabd60206e185c74c61d5862) | | | alleen getallen uit |
![{\displaystyle f(0)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc54adf96acf7e2466de00b7739144d36840108f) | | | alleen getallen uit |
![{\displaystyle f(1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/948f00426d32f835b4cefa1a56aebd8e18ba7d3c) | | | |
![{\displaystyle f(2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65f247dc5542263d64ef5f4346fc7cae009740f4) | | | alleen getallen uit |
![{\displaystyle f(3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bd9b5d7da173a2b3150a2196cb63d4fac80fe23) | | | alleen getallen uit |
![{\displaystyle f(4)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d41b8b27056cdd07af26141da643b6a67b64ddcf) | | | |
![{\displaystyle f(5)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc65fa67fbbfa036e08f6b7f6471eb59df80f8e6) | | | alleen getallen uit |
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
.
Dit levert de volgende matrix op:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3587a5dc315d30559645a2ff52725edcdea5f07c)
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
horend bij de
die volledig ontbinden over de gekozen ontbindingsbasis). Dan staat in iedere rij in de
-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
-waarden −5, −4, −2, −1 en 3. We definiëren daarom
![{\displaystyle x=(7-5)\cdot (7-4)\cdot (7-2)\cdot (7-1)\cdot (7+3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91df44b57653694b2dc772940dfb1b9e0b157306)
![{\displaystyle {\color {White}x}=2\cdot 3\cdot 5\cdot 6\cdot 10}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3294d888bd58f7a51fb1f949dda558745e5015be)
![{\displaystyle {\color {White}x}=1800}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90d24ec0ab5474c29fbc2b9a0c05b7276f4dfc32)
![{\displaystyle {\color {White}x}\equiv 45{\pmod {45}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7253d05539d5336d1d888d9a6893a36e0bb3ed43)
Vervolgens definiëren we
als
![{\displaystyle y={\sqrt {f(-5)\cdot f(-4)\cdot f(-2)\cdot f(-1)\cdot f(3)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2be64eb0c9ffd657720a6a0f458a6b6b86d70be1)
![{\displaystyle {\color {White}y}={\sqrt {-1\cdot 2^{2}\cdot 11\cdots 3^{2}\cdot 11}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7bf79cdb06f7cc6d6c598d32cae47454dff41b12)
![{\displaystyle {\color {White}y}\equiv 45{\pmod {45}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc9f7b564cc8302dc7d3da8b1e14c23f6bedb227)
Er geldt nu dat
, 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
en
te zijn, waaruit volgt dat
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
en
krijgen we de volgende tabel (de niet-gladde functiewaarden zijn weggelaten):
Tabel met waarden en priemfactorontbinding |
![{\displaystyle f(-15)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/94bd89c16d928c7b7f447d1deada8d2653f9b7ea) | | | alleen getallen uit |
![{\displaystyle f(-4)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb7aa168b07af0bf20c4ac8f6d6bf9412bdda685) | | | alleen getallen uit |
![{\displaystyle f(-2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f85ab48a9bda8c96a794fe2ea54b28c736095df6) | | ![{\displaystyle =-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7967bcaaf12f2886567b667bd0f949b050077723) ![{\displaystyle 2^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/efd7711cd907a2d46557a410fb67fc0d84c52ba3) ![{\displaystyle 5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/29483407999b8763f0ea335cf715a6a5e809f44b) | alleen getallen uit |
![{\displaystyle f(0)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc54adf96acf7e2466de00b7739144d36840108f) | | | alleen getallen uit |
![{\displaystyle f(18)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f5f2d02c1f52764d306c91959fbd0f0e285e051) | | ![{\displaystyle 3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/991e33c6e207b12546f15bdfee8b5726eafbbb2f) ![{\displaystyle 5^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ac42c99ce3b9abb17b955f9995dd37ba270905f) | alleen getallen uit |
Hierbij hoort de volgende binaire matrix:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12bac3c30bf2d99d02c2358829774f01aa3306a0)
De tweede tot en met vijfde rij tellen op tot de nulvector, wat leidt tot
![{\displaystyle x=(81-4)\cdot (81-2)\cdot (81+0)\cdot (81+18)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52c984ddc1bce2a79b3481ff78e7d623b9017ca1)
![{\displaystyle {\color {White}x}=77\cdot 79\cdot 81\cdot 99}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e13317cdae90486b690d884a1d66272422877ec0)
![{\displaystyle {\color {White}x}\equiv 2574{\pmod {6501}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/09bd85e8bc724e769b782d44dcd790f5a1563b81)
Na enig rekenwerk volgt
, waaruit volgt
. Dit is geen triviale deler en door uitdelen vinden we snel dat
![{\displaystyle 6501=33\cdot 197=3\cdot 11\cdot 197}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d60a4a8c401d5461565dd0750bee68511952248d)
Complexiteit
De complexiteit van het algoritme wordt in de O-notatie gegeven door
![{\displaystyle O\left(e^{\sqrt {\log {n}\log {\log {n}}}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/355ebca0489fcf06bc63d14b19bf73c80d747680)
Als grondtal voor de logaritme wordt e, het grondtal van de natuurlijke logaritme, gebruikt.
De bovenstaande uitdrukking kan worden herschreven tot
,
een vorm waarin het verschil met de getallenlichamenzeef goed tot uiting komt. Dat algoritme heeft namelijk als complexiteit
,
waar
een constante is met als waarde ongeveer
. Hieruit volgt direct dat voor grote
men beter de getallenlichamenzeef kan gebruiken om een getal te ontbinden.
Voetnoten
- ↑ C Pomerance, A tale of two sieves, Notices of the American Mathematical Society. 43 (1996), 1473-1485.
- ↑ 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.
- ↑ E. Landquist, The Quadratic Sieve Factoring Algorithm, MATH 488: Cryptographic Algorithms, 14 december 2001
- ↑ D. Atkins, M. Graff, A.K. Lenstra, P.C. Leyland, The magic words are squeamish ossifrage