Shors algoritme
Elke keer dat je online bankiert, inlogt op een website of een bericht verstuurt via een beveiligde app, beschermt encryptie die data tegen pottenkijkers. Een groot deel van die beveiliging steunt op één simpel gegeven: het is voor een gewone computer vrijwel onmogelijk om een heel groot getal terug te rekenen naar de twee priemgetallen waaruit het is opgebouwd. Shors algoritme is een rekenmethode voor een kwantumcomputer die dat probleem juist wél snel kan oplossen — en raakt daarmee aan de fundamenten van de digitale beveiliging zoals we die nu kennen.
Vergelijk het met een kluis met miljarden mogelijke combinaties. Een gewone computer moet die, grofweg, één voor één uitproberen; bij grote kluizen duurt dat langer dan het heelal oud is. Shors algoritme, bedacht in 1994 door de Amerikaanse wiskundige Peter Shor, gebruikt eigenaardigheden van de kwantummechanica om in feite veel combinaties tegelijk te doorzoeken. Op een voldoende krachtige kwantumcomputer zou het kraken van zo'n kluis geen miljarden jaren, maar uren kosten. Zulke computers bestaan vandaag nog niet, maar het vooruitzicht alleen al zet cryptografen wereldwijd aan het werk.
Wat is het precies?
Om Shors algoritme te begrijpen, helpt het te weten waarom factoriseren (het ontbinden van een getal in zijn priemfactoren) zo lastig is. Het veelgebruikte versleutelingssysteem RSA werkt met een openbaar getal N dat het product is van twee geheime, zeer grote priemgetallen p en q. Vermenigvuldigen is voor een computer triviaal, maar de omgekeerde weg — uit N de factoren p en q terugvinden — kost met de beste klassieke methodes exponentieel meer tijd naarmate N groter wordt. Bij sleutellengtes die banken en overheden gebruiken (2048 bits) zou dat met huidige computers langer duren dan het universum bestaat.
Shor vond een sluiproute. Hij toonde aan dat factoriseren wiskundig te herleiden is tot het vinden van de "periode" van een bepaalde functie: neem je een willekeurig getal steeds hogere machten en bereken je telkens de rest bij deling door N, dan ontstaat een herhalend patroon. Ken je die herhalingsafstand, dan kun je met een eenvoudige rekenregel (het algoritme van Euclides) de priemfactoren afleiden.
Die periode vinden is voor een klassieke computer nog steeds traag, maar een kwantumcomputer kan het in principe snel. Een qubit, de kwantumversie van een bit, kan dankzij superpositie tegelijk een beetje 0 én een beetje 1 zijn. Door met meerdere qubits tegelijk de functie uit te rekenen, onderzoekt de kwantumcomputer als het ware veel mogelijke uitkomsten tegelijk. Vervolgens past het algoritme een wiskundige truc toe, de kwantum-Fourier-transformatie, die het verborgen periodieke patroon zichtbaar maakt in de kansverdeling van de qubits. Bij de uiteindelijke meting — die de wazige kwantumtoestand laat "instorten" tot een gewone uitkomst — komt met grote waarschijnlijkheid informatie naar boven waarmee de periode, en dus de factoren, te achterhalen zijn. Omdat kwantummetingen kansen betreffen, wordt de berekening enkele keren herhaald en met klassieke rekenstappen gecontroleerd.
Het resultaat: Shors algoritme brengt factoriseren terug van een exponentieel naar een polynomiaal proces. De rekentijd groeit niet meer explosief maar overzichtelijk met de lengte van het getal — het verschil tussen "onmogelijk" en "haalbaar" voor grote getallen.
Wat wil men ermee bereiken?
Onderzoekers bestuderen Shors algoritme om meerdere redenen, niet allemaal gericht op aanvallen. Ten eerste is het een van de duidelijkste bewijzen dat kwantumcomputers in theorie iets kunnen wat klassieke computers niet kunnen bijbenen: een concreet, praktisch relevant probleem met een aantoonbaar exponentieel voordeel. Dat maakt het al dertig jaar een soort ijkpunt voor het hele vakgebied.
Ten tweede is er de veiligheidskant. Omdat RSA en verwante systemen, zoals Diffie-Hellman-sleuteluitwisseling en elliptische-krommecryptografie, hun kracht ontlenen aan precies het probleem dat Shor oplost, zou een werkende, grootschalige kwantumcomputer die versleuteling in principe kunnen breken. Dat vooruitzicht heeft een defensieve onderzoekstak in gang gezet: post-kwantumcryptografie, nieuwe versleutelingsmethodes waarvan wordt aangenomen dat ze ook tegen een kwantumcomputer bestand zijn. Overheden en bedrijven willen die overstap maken vóórdat een aanvaller daadwerkelijk over zo'n machine beschikt.
Die urgentie komt mede door een scenario dat wel "harvest now, decrypt later" wordt genoemd: versleuteld verkeer dat nu wordt onderschept en opgeslagen, kan in de toekomst alsnog worden ontcijferd zodra een geschikte kwantumcomputer bestaat. Voor gegevens die lang geheim moeten blijven — medische dossiers, staatsgeheimen, bedrijfsgeheimen — is dat nu al reden om over te stappen op kwantumbestendige versleuteling, ook al is de dreiging vandaag nog theoretisch.
Voorbeelden uit de praktijk
Shors algoritme is tot nu toe alleen gedemonstreerd op zeer kleine, symbolische getallen, maar die experimenten waren wel belangrijke mijlpalen:
- 2001, IBM Almaden en Stanford University: onderzoekers rond Lieven Vandersypen bouwden een 7-qubit kwantumcomputer op basis van kernspinresonantie (NMR) en lieten daarmee voor het eerst zien dat het getal 15 (= 3 × 5) met Shors algoritme te ontbinden was, gepubliceerd in Nature.
- Rond 2012, University of California, Santa Barbara: de onderzoeksgroep van John Martinis herhaalde de factorisatie van 15, nu met supergeleidende qubits — hetzelfde type qubit dat later de basis vormde voor Googles en IBM's grote kwantumchips.
- 2016, Universiteit Innsbruck: de groep van Rainer Blatt liet met "trapped-ion"-qubits (individuele geladen atomen die met lasers worden vastgehouden) een variant zien die is opgezet om mee te schalen naar meer qubits, in plaats van telkens een specifiek circuit per getal te ontwerpen.
- 2019, IBM en Google: beide bedrijven demonstreerden met hun kwantumchips taken die de grenzen van kwantumhardware verlegden, waaronder Googles "kwantumsuprematie"-experiment met de Sycamore-processor. Dit gebruikte niet Shors algoritme zelf, maar liet wel zien dat het aantal bruikbare qubits en de betrouwbaarheid ervan snel toenamen — bouwstenen die uiteindelijk ook nodig zijn voor een praktische uitvoering van Shors algoritme.
- 2024, NIST (Verenigde Staten): als directe, praktische reactie op de dreiging van Shors algoritme publiceerde het Amerikaanse standaardisatie-instituut NIST de eerste officiële post-kwantumcryptografiestandaarden (FIPS 203, 204 en 205), gebaseerd op wiskundige problemen waarvan gedacht wordt dat ook kwantumcomputers ze niet snel kunnen oplossen.
Hoe ver is de techniek?
De kloof tussen deze experimenten en een echt bedreigende toepassing is enorm. De getallen die tot nu toe met Shors algoritme zijn ontbonden, zijn triviaal klein — een schoolkind kan ze zonder rekenmachine factoriseren. Het probleem zit niet zozeer in het aantal qubits op zich, maar in de kwaliteit ervan: huidige qubits zijn foutgevoelig en verliezen hun kwantumtoestand (decoherentie) al na fracties van een seconde tot enkele milliseconden.
Om dat op te lossen, moeten meerdere onbetrouwbare "fysieke" qubits worden gecombineerd tot één betrouwbare "logische" qubit via kwantumfoutcorrectie. Onderzoekers Craig Gidney en Martin Ekerå schatten in een veelgeciteerde studie (2019, later gepubliceerd in het tijdschrift Quantum) dat het kraken van een 2048-bit RSA-sleutel met realistische foutenpercentages ongeveer 20 miljoen fysieke qubits en zo'n acht uur rekentijd zou vereisen. Ter vergelijking: de grootste huidige chips, zoals IBM's "Condor" (aangekondigd eind 2023, iets meer dan duizend supergeleidende qubits), zitten nog vele ordes van grootte onder dat aantal — en zijn bovendien niet foutgecorrigeerd.
De ontwikkeling gaat wel gestaag: het aantal qubits in onderzoekssystemen groeit en fabrikanten leggen inmiddels meer nadruk op foutpercentages en logische qubits dan op ruwe aantallen. Toch zijn schattingen voor wanneer een cryptografisch relevante kwantumcomputer er staat sterk uiteenlopend en onzeker: sommige experts noemen tien tot twintig jaar, anderen achten het nog veel verder weg of zelfs onzeker of het ooit op de benodigde schaal lukt. Er is geen wetenschappelijke consensus over een concrete datum — een eerlijke onzekerheid die in nieuwsberichten vaak wordt gladgestreken.
Wie werken eraan?
Het onderzoek naar kwantumcomputers — en indirect naar de haalbaarheid van Shors algoritme — vindt wereldwijd plaats, verspreid over bedrijven, universiteiten en overheidsinstanties.
In de Verenigde Staten investeren IBM (met chips als Condor en Heron), Google Quantum AI (de Sycamore- en Willow-processoren), Microsoft (dat inzet op een fundamenteel ander, foutbestendiger type qubit) en gespecialiseerde spelers als IonQ en Quantinuum (beide met trapped-ion-technologie) fors in hardware. Het Amerikaanse standaardisatie-instituut NIST trekt de kar op het gebied van post-kwantumcryptografie.
China investeert eveneens zwaar, met de University of Science and Technology of China (USTC) in Hefei als belangrijkste onderzoekscentrum; die groep bouwde onder meer de fotonische kwantumcomputer "Jiuzhang" en de supergeleidende chip "Zuchongzhi". In Europa is QuTech — een samenwerking tussen de TU Delft en TNO — een van de belangrijkste kwantumonderzoeksinstituten, actief op zowel hardware als (post-)kwantumveilige cryptografie. Ook de Europese Unie financiert via het Quantum Flagship-programma onderzoek in meerdere lidstaten. Peter Shor zelf werkt tegenwoordig als hoogleraar toegepaste wiskunde aan het Massachusetts Institute of Technology (MIT).