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. 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 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  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 
Om het samengestelde getal  te ontbinden in priemfactoren, definieert men met de entierfunctie

de functie

Dan zoekt men een rij getallen  zodanig dat  een kwadraat is modulo . Als dat zo is, kan deze uitdrukking als definitie voor  genomen worden
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.

Aanvullende opmerkingen 
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). Het kraken van RSA-129 gebeurde ook met deze methode.

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

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

Dit levert op:
{| class="wikitable"
!colspan="4" | 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
,
geldt

De laatste stap zegt nu:

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

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:
{| class="wikitable"
!colspan="4" | 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 
Voor  en  krijgen we de volgende tabel (de niet-gladde functiewaarden zijn weggelaten):

{| class="wikitable"
!colspan="4" | 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 
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.

Algoritme
Getaltheorie