Het algoritme van Shor is de reden dat Q-Day bestaat. Uitgevonden door wiskundige Peter Shor in 1994, meer dan een decennium voordat een quantumcomputer krachtig genoeg was om het uit te voeren, beschrijft het exact hoe een quantumcomputer grote getallen exponentieel sneller kan factoriseren dan welke klassieke machine dan ook. Omdat RSA-encryptie, de beveiligingsstandaard die het grootste deel van het internet beschermt, zijn kracht ontleent aan de moeilijkheid van het factoriseren van grote getallen, is het algoritme van Shor de directe dreiging. Het begrijpen ervan is begrijpen waarom de cryptografische migratie die momenteel plaatsvindt niet optioneel is.
Waarom RSA afhankelijk is van de moeilijkheid van factoriseren
RSA-encryptie werkt vanwege een wiskundige asymmetrie: het is triviaal om twee grote priemgetallen te vermenigvuldigen, maar buitengewoon moeilijk om het resultaat terug te factoriseren in zijn componenten. Het genereren van een RSA-sleutelpaar duurt een fractie van een seconde. Het kraken ervan door de priemfactoren te vinden van het resulterende 2048-bits getal zou op de snelste klassieke supercomputer, met het beste bekende klassieke algoritme, langer duren dan de huidige leeftijd van het universum.
De kern van het algoritme: factoriseren is periodiek
De centrale inzicht van Shor was dat het probleem van het factoriseren van een getal N kan worden herleid tot een ander probleem: het vinden van de periode van een wiskundige functie. Voor een willekeurig gekozen getal a (kleiner dan N) is de functie f(x) = aˣ mod N periodiek, ze doorloopt waarden en herhaalt zich uiteindelijk. Als je de periode r kunt vinden, kun je die gebruiken om de factoren van N te berekenen. Het factoriseringsprobleem wordt een periodezoekopdracht.
Interactief: het algoritme van Shor op het getal 15
- Het doel. Splits N = 15 in zijn twee priemfactoren. De truc van Shor: kies een getal, hier a = 7, en kijk naar f(x) = 7ˣ mod 15, de rest als je 7ˣ deelt door 15. Weet je na hoeveel stappen die reeks zich herhaalt, dan volgen de factoren vanzelf.
- Een gewone computer probeert x één voor één. 7⁰ = 1, 7¹ = 7, 7² = 49 geeft rest 4, 7³ geeft rest 13 en 7⁴ weer rest 1. Het patroon herhaalt zich elke 4 stappen: de periode is r = 4. Bij een RSA-getal van 2048 bits is de periode zo lang dat waarde voor waarde zoeken langer duurt dan het heelal oud is.
- Een quantumcomputer rekent alle x tegelijk uit. Met 4 qubits bevat het invoerregister alle 16 waarden van 0 tot en met 15 in superpositie, en één doorgang van het circuit rekent f voor allemaal uit. Maar als je nu meet, zie je maar één willekeurige waarde. Het antwoord zit in het patroon, niet in één losse waarde.
- Interferentie maakt de periode zichtbaar. De quantum-Fouriertransformatie laat de delen die niet in het ritme passen tegen elkaar wegvallen en de rest elkaar versterken. Er blijven pieken over op 0, 4, 8 en 12: veelvouden van 16 ÷ r. Een meting geeft bijvoorbeeld 12. Dan is 12/16 = 3/4, dus r = 4. (Komt er 0 uit, dan weet je niets en draai je hem gewoon opnieuw.)
- Gewone wiskunde doet de rest. Met r = 4: 7² = 49, en de grootste gemeenschappelijke deler (ggd) van 48 en 15 is 3, die van 50 en 15 is 5. Dus 15 = 3 × 5. Voor RSA-2048 vraagt hetzelfde recept een quantumcomputer met minder dan een miljoen foutgevoelige qubits die minder dan een week rekent (Gidney, 2025); de grootste machines van nu zijn daar nog ver van af.
Stap voor stap: hoe het algoritme werkt
RSA-250, een getal van 250 cijfers uit de RSA-challenge, werd op 28 februari 2020 gefactoriseerd. Dat kostte ongeveer 2.700 core-jaren rekentijd (één core-jaar is één processorkern die een vol jaar rekent). In september 2026 vielen twee grotere getallen uit de challenge op gewone, klassieke hardware. Eric Lu van Cognition factoriseerde RSA-260, een getal van 260 cijfers, in ongeveer 13,5 GPU-jaren (één GPU-jaar is één grafische processor die een vol jaar rekent). Stephen Weis van Anthropic factoriseerde RSA-896, een getal van 896 bits, in ongeveer 30 GPU-jaren op maximaal 2.048 grafische processors. Een RSA-2048-getal heeft 2.048 bits, oftewel 617 cijfers: ruim twee keer zo lang. Aan de quantumkant schatten Craig Gidney en Martin Ekerå in 2019 dat RSA-2048 te factoriseren is in 8 uur met 20 miljoen qubits met ruis. In mei 2025 bracht Gidney dat terug tot minder dan een miljoen qubits met ruis in minder dan een week. Geen enkele quantumcomputer komt vandaag in de buurt van een van beide getallen.
Wat het algoritme van Shor wel en niet breekt
Het algoritme van Shor bedreigt specifiek RSA en elliptische-curvecryptografie (ECC), beide afhankelijk van wiskundige problemen (geheel-getal-factorisering en discrete logaritmen) die Shor efficiënt kan oplossen. Het breekt symmetrische encryptie zoals AES niet direct. Het algoritme van Grover kan een ongesorteerde database kwadratisch sneller doorzoeken, waardoor het effectieve beveiligingsniveau van een symmetrische sleutel wordt gehalveerd. AES-256 daalt naar ruwweg AES-128-equivalent beveiliging, wat nog steeds als veilig wordt beschouwd.
De praktische implicatie: elke HTTPS-verbinding, certificaatautoriteit, VPN, codehandtekening en cryptocurrency-portemonnee die afhankelijk is van RSA of ECC is theoretisch kwetsbaar. NISTs post-quantum standaarden, ML-KEM, ML-DSA, FN-DSA en SLH-DSA, zijn ontworpen als quantumresistente vervangingen. Migreren naar deze standaarden vóórdat een cryptografisch relevante quantumcomputer arriveert is de gehele Y2Q-uitdaging.