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]

Grondgedachte[bewerken]

Het achterliggende idee van de kwadratische zeef is modulair rekenen.[2] en berust op de voorstelling van een getal als verschil van twee kwadraten:

.

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

In dat geval geldt namelijk dat

waaruit direct volgt

Als deze grootste gemene delers beide niet gelijk zijn aan 1, zijn er twee niet-triviale factoren, dat wil zeggen niet 1 en niet , gevonden. Op die factoren kan, als ze niet al allebei zelf priem zijn, hetzelfde procedé toegepast worden om een priemfactorontbinding van 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 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[bewerken]

Stel dat we het samengestelde getal willen ontbinden in priemfactoren. We bepalen dan allereerst met de entierfunctie en definiëren de functie

Nu zoeken we een rij getallen zodanig dat een kwadraat is modulo . Als dat zo is, dan kunnen we deze uitdrukking als definitie voor nemen omdat 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 formeel gedefinieerd als

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 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 zoals hierboven gedefinieerd is niet de enige die werkt. Eventueel kunnen we ook

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

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

Feitelijk voldoen veel veeltermen van de vorm

In de praktijk kiest men en zodanig dat een veelvoud is van , zeg ofwel

De veelterm is dan te herschrijven als

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

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[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 en geldt dat de entier van gelijk is aan . We definiëren nu de veelterm . We definiëren verder en . Dan krijgen we en

Dit levert op:

Tabel met waarden en priemfactorontbinding
Alleen getallen uit
Alleen getallen uit
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

We nemen dus

Merk op dat ook geldt

en evenzo

Als we nemen

dan geldt

De laatste stap zegt nu:

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

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
Alleen getallen uit
Alleen getallen uit
Alleen getallen uit
Alleen getallen uit
Alleen getallen uit
Alleen getallen uit
Alleen getallen uit
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:

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

Vervolgens definiëren we als

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

Voor , , en krijgen we de volgende tabel (de niet-gladde functiewaarden zijn weggelaten):

Tabel met waarden en priemfactorontbinding
Alleen getallen uit
Alleen getallen uit
Alleen getallen uit
Alleen getallen uit
Alleen getallen uit

Hierbij hoort de volgende binaire matrix:

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

Na enig rekenwerk volgt waaruit volgt . Dit is geen triviale deler en door uitdelen vinden we snel dat

Complexiteit[bewerken]

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

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.