Mathematik mit Licht

Bei der Zerlegung großer Zahlen in ihre Primfaktoren scheitern selbst die schnellsten Computer. Abhilfe verspricht ein raffiniertes Verfahren, bei dem man die Schwingungen kalter Atome und kurzer Laserpulse nutzt.

Von Rainer Scharf

Die abhörsichere elektronische Datenübertragung beruht heutzutage meist auf einem Verfahren, das man Public-Key-Kryptographie nennt. Hierbei verwenden die miteinander kommunizierenden Parteien zwei Schlüssel, einen öffentlichen und einen geheimen privaten Schlüssel. Der Sender codiert seine zu übermittelnden Daten mit dem öffentlichen Schlüssel und macht sie dadurch unleserlich. Der Empfänger bringt die Botschaft mit seinem geheimen Schlüssel wieder zum Vorschein. Als öffentlichen Schlüssel nimmt man üblicherweise eine Zahl mit vielen Dezimalstellen, die sich als Produkt zweier großer Primzahlen - also Zahlen, die nur durch 1 und sich selbst teilbar sind - darstellen lässt. Die beiden Primzahlen - der geheime Schlüssel - sind nur dem Empfänger bekannt. Bislang gilt dieses Verfahren als sicher. Denn obwohl es keine Schwierigkeit bereitet, sogar zwei riesige Primzahlen miteinander zu multiplizieren, würde es den modernsten Elektronenrechnern sogar in Jahrmillionen nicht gelingen, die beiden Primzahlen aus dem Produkt selbst zu ermitteln. Doch das könnte sich mit neuartigen Computern und ausgeklügelten Rechenverfahren vielleicht bald ändern, wie neuere Untersuchungen nahelegen.
 

Der Aufwand bei der Zerlegung einer Zahl in ihre Primfaktoren nimmt rasch mit der Größe der Zahl zu. Deshalb benötigt man für entsprechende Rechnungen leistungsfähige Computer und effiziente Verfahren, die möglichst viele Rechenoperationen parallel ausführen können. Ein Quantencomputer etwa, der die Gesetze der Quantenphysik effizient nutzen und einige hundert "Quantenbits" verarbeiten würde, könnte Zahlen mit hundert Dezimalstellen in Sekundenbruchteilen in ihre Primfaktoren zerlegen. Einen entsprechenden Algorithmus für einen Quantencomputer hat 1994 der amerikanische Informatiker Peter Shor vorgeschlagen. Noch liegt die Verwirklichung einer solchen Rechenmaschine in weiter Ferne, und so sucht man nach anderen Möglichkeiten, eine Lösung zu finden.

Ein erfolgversprechendes Verfahren haben im Jahr 2006 Forscher um Wolfgang Schleich von der Universität Ulm ersonnen. Dabei werden die Primfaktoren einer vorgegebenen Zahl N mit Hilfe von Gaußschen Summen ermittelt. Dank einer solchen Summe kann man testen, ob N durch eine andere, kleinere Zahl k teilbar ist. Die Gaußsche Summe besteht aus mehreren Summanden, die von N und k abhängen. Normalerweise heben sich die Summanden gegenseitig auf, und der Betrag der Summe ist nahezu null. Ist jedoch N durch k teilbar, so haben alle Summanden der Gaußschen Summe ein und dasselbe Vorzeichen, so dass der Betrag der Summe einen großen Wert annimmt. Auf diese Weise lassen sich sämtliche Teiler einer Zahl und damit auch deren Primfaktoren ermitteln.

Für herkömmliche Computer ist diese Rechenmethode allerdings zu umständlich. Deshalb nutzt man aus, dass sich die Summanden einer Gaußschen Summe wie Wellen oder Schwingungen verhalten. Man "berechnet" die Summe gewissermaßen dadurch, dass man Schwingungen oder Wellen überlagert und das resultierende Interferenzsignal misst. Falls eine vorgegebene Zahl durch eine andere Zahl teilbar ist, verstärken sich die betreffenden Wellen oder Schwingungen, und es tritt konstruktive Interferenz auf. Andernfalls löschen sie sich aus. Mit dieser Technik gelang es Forschern der Universität Stuttgart im vergangenen Jahr, die Zahl 157 573 in ihre Primfaktoren zu zerlegen. Dazu hatte man die Spins von Wasserstoffkernen durch Kernspinresonanz zu Schwingungen angeregt und das Interferenzsignal gemessen. Immer dann, wenn die eine Zahl die andere teilte, war das Signal besonders stark. Auf diese Weise ließen sich die Primfaktoren 13, 17, 23 und 31 ermitteln.

Zwei Forschergruppen aus Deutschland und Frankreich haben jetzt ähnliche Experimente mit kalten Atomen beziehungsweise Lichtpulsen ausgeführt und dadurch experimentelles Neuland betreten. Wie Michael Gilowski von der Universität Hannover und seine Kollegen in der Zeitschrift "Physical Review Letters" (Bd. 100, Nr. 030201) berichten, haben sie Schwingungen in den Elektronenhüllen kalter Rubidiumatome dazu benutzt, die Zahl 263 193 in die Primfaktoren 3, 7, 83 und 151 zu zerlegen. Die Atome ließen sie aus einer sogenannten magnetooptischen Falle entweichen und brachten sie dann mit unterschiedlich langen Folgen von Laserpulsen in verschiedene Schwingungszustände. Deren Form hing von der Zahl ab, die daraufhin geprüft werden sollte, ob sie ein Teiler von 263 193 ist oder nicht. Aus etwa fünf atomaren Schwingungszuständen erzeugten die Forscher ein Interferenzsignal. Dieses war besonders intensiv, wenn die ausgewählte Zahl tatsächlich ein Teiler war. Die Suche nach den Primfaktoren erfolgte noch Schritt für Schritt, denn die in Frage kommenden Zahlen wurden der Reihe nach getestet. Gilowski und seine Kollegen hoffen, dass mit quantenmechanisch verschränkten und damit stark korrelierten Atomen, die in Lichtgittern festgehalten werden sollen, sich viele Teilerkandidaten parallel überprüfen lassen. Damit könnten die Primfaktoren viel schneller berechnet werden.

Die Forscher um Damien Bigourd von der Université de Toulouse verwendeten zur Primfaktorzerlegung der Zahl 15 251 ultrakurze Laserpulse. Diesen wurden mit einem Pulsformer unterschiedliche Phasen aufgeprägt, die vom ausgewählten Teilerkandidaten abhingen ("Physical Review Letters" Bd. 100, Nr. 030202). Anschließend wurden jeweils neun der Pulse zur Überlagerung gebracht, und die resultierende Lichtwelle wurde mit einem Spektrometer analysiert. Wieder gab es für bestimmte Teilerkandidaten ein besonders intensives Signal, und zwar für 101 und 151, die Primfaktoren von 15 251. Die französischen Forscher hoffen ebenfalls, ihr Verfahren noch wesentlich beschleunigen zu können. Durch eine geeignete Wahl der Frequenzen, Phasen und Entstehungszeiten der Lichtpulse könnte man für eine vorgegebene Zahl eine Lichtwelle erzeugen, aus der sich alle Primfaktoren dieser Zahl auf einen Schlag ablesen ließen. Solange aber nur vergleichsweise kleine Zahlen mit Hilfe von Schwingungen und Wellen faktorisiert werden können, ist die Sicherheit der gängigen Verschlüsselungsverfahren noch nicht gefährdet.

Text: F.A.Z., 06.02.2008, Nr. 31 / Seite N2