Shors algoritm
Faktoriserar stora tal i polynomisk tid — och gör därmed RSA och elliptiska kurvor obrukbara den dag hårdvaran finns.
Peter Shor publicerade algoritmen 1994 vid Bell Labs. Den var det första övertygande beviset för att kvantdatorer kan lösa ett praktiskt viktigt problem exponentiellt snabbare än kända klassiska metoder, och den förvandlade fältet från teoretisk kuriositet till något myndigheter finansierar.
Kärnan är oväntad: faktorisering skrivs om till att hitta perioden hos en funktion, och periodicitet är precis vad kvant-fouriertransformen är bra på. Att bryta RSA-2048 uppskattas kräva i storleksordningen tusentals felrättade logiska qubitar, alltså miljontals fysiska — långt bortom dagens maskiner, men nära nog för att migreringen till post-quantum-kryptografi pågår redan.