Quanten als Codeknacker: Physiker haben eine Methode entwickelt, mit der sich Zahlen einfacher und schneller als bisher von Quantencomputern in Primzahlen zerlegen lassen. Sie modifizierten dafür den sogenannte Shor-Algorithmus und setzten ihn in einem Ionenfallen-Quantencomputer so effizient um, dass er nun auch für größere Zahlen anwendbar wird, wie die Forscher im Fachmagazin „Science“ berichten.
Jede natürliche Zahl lässt sich als Produkt von Primzahlen darstellen. Für kleine Zahlen ist die Primfaktorzerlegung nur eine Denksportaufgabe, bei großen Zahlen erweist sie sich aber als extrem aufwändig. Darauf beruhen heute gängige Verschlüsselungsverfahren wie das RSA-Kryptosystem. Weil klassische Computer an der Primfaktorzerlegung großer Zahlen sehr lange rechnen, galt dieses Verfahren bisher auch als sehr sicher.
Quanten als Primzahl-Knacker
1994 hat der amerikanische Mathematiker und Informatiker Peter Shor jedoch einen Algorithmus entwickelt, der mithilfe eines Quantencomputers die Primfaktoren sehr viel rascher findet. Weil ein Quantencomputer durch die Überlagerung von Zuständen stärker parallel rechnet als klassische Computer, kann er solche Aufgaben schneller bewältigen. Um die Zahlen speichern und die Primfaktoren berechnen zu können, benötigt er allerdings entsprechend viele Quantenbits.
Dies erweist sich heute noch als schwierig, denn die im Labor existierenden Quantenrechner auf der Basis von Photonen und anderen Teilchen verfügen nur über wenige Quantenbits. In den vergangenen 15 Jahren wurde der Shor-Algorithmus im Labor daher zwar schon mit unterschiedlichen Technologien demonstriert – allerdings nicht ohne das Ergebnis schon von vornherein vorauszusetzen und nur für kleine Zahlen.
