Der Shor-Algorithmus ist einer der bekanntesten Quantenalgorithmen, weil er ein fundamentales Problem der Informatik löst: die Zerlegung großer Zahlen in ihre Primfaktoren. Während klassische Computer für diese Aufgabe bei sehr großen Zahlen extrem viel Zeit benötigen, nutzt der Shor-Algorithmus die Quantenmechanik, um den Rechenaufwand drastisch zu reduzieren.
Die Grundidee hinter Shors Ansatz besteht darin, das Faktorisierungsproblem auf die periodische Funktion eines modularen Exponentials zurückzuführen. Mittels Quanten-Fourier-Transformation wird diese Periode effizient bestimmt, woraus sich mit hoher Wahrscheinlichkeit die gesuchten Primfaktoren ableiten lassen. So kann ein Quantencomputer Zahlen faktorisieren, die für klassische Rechner praktisch unknackbar sind.
Die Bedeutung des Shor-Algorithmus geht weit über reine Mathematik hinaus: Viele gängige kryptografische Verfahren wie RSA beruhen darauf, dass das Faktorisieren großer Zahlen schwierig ist. Ein hinreichend leistungsfähiger Quantencomputer, der Shors Algorithmus ausführt, würde diese Verschlüsselungen brechen können. Deshalb treibt die Erkenntnis aus Shors Arbeit die Entwicklung postquantenkryptografischer Verfahren sowie die Forschung zu Fehlerschutz und Skalierung von Quantencomputern
