Indischer Zahlenzauber

Ein effizientes Primzahlensieb könnte indirekt die im Online-Handel übliche asymmetrische Verschlüsselung obsolet werden lassen

Das im elektronischen Zahlungsverkehr – beispielsweise beim Einkaufen im Internet – genutzte asymmetrische Verschlüsselungsprinzip setzt stillschweigend voraus, dass es keinen effizienten Algorithmus zur Primfaktorzerlegung gibt; tumbes Durchprobieren gilt als ineffizient. Überraschenderweise gibt es nunmehr einen effizienten Algorithmus zum Prüfen, ob eine Zahl prim ist; die Rechenzeit variiert polynomial statt exponentiell mit der Zahl der Ziffern des Primzahlkandidaten. Somit ließe sich über die Zukunft der asymmetrischen Kryptographie spekulieren.

"Die wahre Mathematik hat keine Auswirkungen auf den Krieg. Noch niemand hat bis jetzt einen wie auch immer gearteten kriegerischen Zweck der Zahlentheorie oder der Relativitätstheorie entdecken können, und es ist sehr unwahrscheinlich, dass dies in den nächsten Jahren geschehen wird." Das prophezeite der amerikanische Zahlentheoretiker G. H. Hardy im Jahr 1940 in seinem Buch A Mathematican's Apology.

Wie sich hier wieder einmal zeigt, sind Voraussagen schwierig – vor allem dann, wenn sie die Zukunft betreffen. Der erste Aspekt ist mit der Entdeckung der asymmetrischen Kryptographie, die sich selbstverständlich militärisch nutzen lässt, inzwischen überholt, der zweite war es schon ein Jahr vorher, nämlich 1939, nachdem Einstein seinen später bereuten Brief an Roosevelt und Heisenberg einen brisanten Bericht ans Heereswaffenamt geschickt hatte.

Vom Nutzen des Nutzlosen

Die zur Primfaktorzerlegung nötige Rechenzeit variiert nicht polynomial, sondern exponentiell mit der Zahl der Ziffern, im folgenden z genannt. Ein millionenfach schnellerer Rechner steigert die Größe zerlegbarer Zahlenmonster folglich nur um wenige Ziffern.

Um zu entscheiden, ob eine zu testende Zahl prim ist, probiert man alle natürlichen Zahlen als Teiler durch, bis die Quadratwurzel der zu testenden Zahl erreicht ist; sollte es einen größeren Teiler geben, dann muss der andere wiederum kleiner als dieser Schwellwert sein. Das durchprobieren dauert eine Zeitspanne, die proportional zu 10^(z/2) ist, da der Test abbricht, nachdem die Quadratwurzel der zu testenden Zahl erreicht ist, daher der Faktor 1/2 im Exponenten. Dieses tumbe Vorgehen ist ineffizient, da die erforderliche Rechenzeit eine Exponentialfunktion der Zahl der Ziffern ist.

Es gibt unendlich viele Primzahlen, die bisher größte bekannte ist 2^25.964.951-1 und hat 7.816.230 Ziffern. Primzahlkandidaten, die eine um 1 verminderte Zweierpotenz sind, lassen sich mit einem speziell für diese Sonderfälle entwickelten Algorithmus prüfen.

Derzeitiger Primzahlen-Rekord ist eine Zahl mit 7.816.230 Ziffern – ein Sonderfall

Die exponentielle Abhängigkeit treibt den Rechenaufwand für Zahlen mit deutlich über 100 Ziffern an die Grenze des technisch möglichen. Nach wie vor glauben die meisten Mathematiker, es gebe keinen Algorithmus zur Primfaktorzerlegung, dessen Rechenzeit polynomial – also beispielsweise linear, quadratisch oder kubisch – mit der Anzahl z der Ziffern variiert. Bisher schien das auch für den Primzahltest zu gelten.

Eine Arbeitsgruppe indischer Mathematiker an der Technischen Hochschule in Kanpur hat nunmehr einen effizienten Primzahlentestalgorithmus gefunden, bei dem die Rechenzeit polynomial mit der Anzahl z der Ziffern des Zahlenmonsters variiert. Bei bisherigen Algorithmen war die Rechenzeit eine Exponentialfunktion, insofern ist der Fortschritt der Inder dramatisch, wenn er auch keine Primfaktorenzerlegung liefert, so dass Amazon, Ebay & Co zunächst wie gehabt weiter machen können. Die Wissenschaftler berichten ihren Ansatz in der Fachzeitschrift Annals of Mathematics in Band 160 (2005) auf Seite 781. Eine drei Jahre alte Vorabversion mit dem Titel Primes is in P lässt sich von der erwähnten Website als Postscript-Datei herunterladen und mittels Acrobat Distiller ins PDF-Format ummodeln.

Das Prinzip beruht auf einem Lehrsatz des als Hobby-Mathematiker berühmt gewordenen gelernten Volljuristen Pierre de Fermat, an dessen sogenannten letzten Theorem sich Mathematiker über Jahrhunderte die Zähne ausbissen, was aber nichts mit dem Thema dieses Artikels zu tun hat. Der Lehrsatz besagt: Wenn p eine Primzahl ist, dann gilt für jede beliebige Zahl a kleiner als p, dass die Zahl a^(p-1)-1 durch p teilbar ist. Dummerweise gilt die Umkehrung nicht. Der Lehrsatz bildet also nur einen Grobfilter, den alle Primzahlkandidaten erst einmal durchlaufen müssen, und eine Verfeinerung, welche die indische Arbeitsgruppe fand, entscheidet schließlich über die Primzahleigenschaft.

Quantium inside

Offen bleibt die Frage, ob nicht vielleicht doch irgendein Schlapphut schlauer als alle Mathematiker in den Elfenbeintürmen sein könnte und einen effizienten Primfaktorzerlegungsalgorithmus bereits einsetzt. Wäre eine effiziente Primfaktorzerlegung von Zahlen mit über 200 Ziffern technisch möglich, so erzwänge dies ein neuartiges Verschlüsselungsprinzip für den elektronischen Zahlungsverkehr.

Ian Stewart bemerkt in der Ausgabe vom 6. August 2005 des Magazins New Scientist auf Seite 40 ironisch, einen solchen Algorithmus gäbe es bereits, der an den Bell Labs tätige Wissenschaftler Peter Shor hätte ihn im Jahr 1995 gefunden. Nur ein kleiner Schönheitsfehler: Der Algorithmus liefe nur auf einem Quantencomputer. Ian Stewart lehrt Mathematik an der Universität von Warwick und ist nebenberuflich Hofmathematiker des Scientific American.