Atome und Licht auf Primfaktorensuche

Zwei Forschergruppen haben die Primfaktorzerlegung mit kalten Atomen bzw. Lichtpulsen durchgeführt. Beide Verfahren beruhen auf den mathematischen Eigenschaften Gaußscher Summen.

Während sich zwei 100-stellige Primzahlen problemlos miteinander multiplizieren lassen, ist die Zerlegung dieses Produktes mit einem herkömmlichen Computer nahezu unmöglich, wenn man die Faktoren nicht kennt. Diese Asymmetrie nutzt die Public Key Cryptography. Ein Quantencomputer, der mit hunderten von verschränkten Qubits rechnet, könnte mit einem von Peter Shor 1994 vorgeschlagenen Verfahren noch wesentlich größere Primzahlprodukte „knacken“. Doch solch einen Computer gibt es noch nicht. Mit einem alternativen Verfahren, das die Interferenz von Wellen nutzt, war im vergangenen Jahr die Zahl 157.573 durch Kernspinresonanz in ihre Faktoren zerlegt worden. Jetzt haben zwei Forschergruppen kalte Atome bzw. Lichtpulse für die Faktorenzerlegung mit Wellen eingesetzt.

Das Verfahren beruht auf den mathematischen Eigenschaften Gaußscher Summen und auf der Möglichkeit, solche Summen mit interferierenden Wellen auswerten zu können. Um die Primfaktoren der natürlichen Zahl N zu finden, bildet man demnach den arithmetischen Mittelwert der komplexen Zahlen exp(–2πim ² N/k), wobei das ganzzahlige m von 0 bis M≈N ^1/4 läuft, während das ganzzahlige k festgehalten wird. Was für diese Gaußsche Summe A _N(k) herauskommt, hängt davon ab, ob k die Zahl N teilt oder nicht. Ist k ein Teiler von N, so gilt für alle Summanden exp(–2πim ² N/k)=1 und damit auch A _N(k)=1. Wenn k und N teilerfremd sind, so haben die Summanden sehr unterschiedliche Phasen und löschen sich gegenseitig weitgehend aus. Dann ist ihre Summe A _N(k) betragsmäßig viel kleiner als 1.

Um auf diese Weise die Primfaktoren von N zu ermitteln, muss k alle Werte von 1 bis etwa N ^1/2 durchlaufen. Auf einem herkömmlichen Computer installiert, brächte dieses Verfahren keine Vorteile. Präpariert man jedoch eine große Zahl von Wellen, die die gleiche Intensität aber unterschiedliche Phase exp(–2πim ² N/k) haben, und lässt diese Wellen dann kontrolliert interferieren, so kann man dem Ausgangssignal entnehmen, für welche Werte von k die Interferenz konstruktiv ist. Diese k-Werte sind dann die Teiler von N. Solch ein Interferenzexperiment haben Michael Gilowski von der Universität Hannover und seine Kollegen sowie Damien Bigourd von der Université de Toulouse und seine Mitarbeiter durchgeführt, beide in Kooperation mit der Gruppe von Wolfgang Schleich in Ulm.

Die Forscher in Hannover haben kalte Rubidiumatome benutzt, um N = 263.193 = 3×7×83×151 in Primfaktoren zu zerlegen. Die Atome ließen sie aus einer magneto-optischen Falle entweichen und brachten sie durch einen Laserpuls in eine kohärente Überlagerung zweier Hyperfeinzustände. Anschließend wurden die Atome (m+1) weiteren Laserpulsen ausgesetzt, die den beiden Zuständen eine zu m ² proportionale Phasendifferenz gaben. Ein abschließender Laserpuls wandelte die Phasendifferenz in einen Populationsunterschied zwischen den beiden Hyperfeinzuständen um, dem man das Interferenzsignal cos(2πm ² N/k) entnehmen konnte.

Die Interferenzsignale für unterschiedlich lange Pulsfolgen mit 0 =m=M wurden addiert und ergaben den Realteil der gesuchten Gaußsumme. Dann wurden auch noch die k-Werte zwischen 1 und 200 variiert und die sich ergebenden Gaußsummen verglichen. Es zeigte sich, dass eine maximale Pulsfolgenlänge von M=5 schon ausreichte, um anhand der Gaußschen Summen die Teiler von 263.193 zweifelsfrei zu ermitteln. Während diese Bestimmung der Primfaktoren noch sequenziell war, hoffen die Forscher, mithilfe von verschränkten Atomen in optischen Gittern eine massiv parallele Berechnung durchführen zu können. Das aktuelle Experiment sehen sie als ersten Schritt in diese Richtung.

Ihre Kollegen in Toulouse haben N = 15.251 = 101×151 mithilfe von Femtosekundenpulsen in Primfaktoren zerlegt. Dazu haben sie den einzelnen Lichtpulsen mit einem Pulsformer jeweils die Phase exp(–2πim ² N/k) aufgeprägt und neun Pulse mit m=0,...8 zur Interferenz gebracht. Das Interferenzsignal, das sie mit einem hochauflösenden Spektrometer analysierten, ergab dann die gewünschte Gaußsche Summe. Bei Variation von k zeigten die Beträge der Gaußschen Summen für k=101 und 151 deutliche Maxima. Die Forscher glauben, dass sich ihr Verfahren noch wesentlich beschleunigen lässt. So könnte man durch Veränderung der Pulsfrequenz und der Pulszeiten dem optischen Signal unterschiedliche Werte für N und k aufprägen. Das Spektrum des Signals enthielte dann Informationen über eine große Zahl von Gaußschen Summen gleichzeitig, sodass auch auf diese Weise eine massiv parallele Berechnung der Primfaktoren möglich wäre.

Rainer Scharf

Weitere Infos:

• Originalveröffentlichungen:
  M. Gilowski et al.: Gauss Sum Factorization with Cold Atoms. Phys. Rev. Lett. 100, 030201 (2008).
  http://dx.doi.org/10.1103/PhysRevLett.100.030201
  http://arxiv.org/abs/0709.1424
• Damien Bigourd et al.: Factorization of Numbers with the Temporal Talbot Effect: Optical Implementation by a Sequence of Shaped Ultrashort Pulses. Phys. Rev. Lett. 100, 030202 (2008).
  http://dx.doi.org/10.1103/PhysRevLett.100.030202
  http://arxiv.org/abs/0709.1906v2
• Gruppe von Wolfgang Ertmer:
  http://www.iqo.uni-hannover.de/ertmer/
• Gruppe von Wolfgang Schleich:
  http://www.physik.uni-ulm.de/quan/