ürlich auch für die Musik oder bildende Kunst gültig. Will man aber einen gebildeten Nichtmathematiker die Schönheit unserer Kunst genießen lassen, so muss man vielleicht doch bei Euklid – oder jedenfalls nicht später als in der Renaissance – anfangen. Schon die Höhepunkte des 19. Jahrhunderts sind ohne einige Vorarbeit kaum zugänglich, und die Künste von Andrew Wiles, der 1994 den Beweis für den Großen Fermatschen Satz gefunden hat, sind auch für die Mehrheit der Fachleute mysteriös.Schön und schnell rechnenEs ist nicht abwegig zu sagen, dass unter allen mathematischen Disziplinen die Zahlentheorie die eigentliche Grundlage und der Nährboden ist. Viele der schönsten Früchte der mathematischen Kunstfertigkeit sind mit der Zahlentheorie verbunden – und unterliegen damit dem genannten ästhetischen Vermittlungsproblem. Aber trotzdem leisten zahlentheoretische Ideen und Sätze auch einen wesentlichen und für uns alle nützlichen Beitrag in der Informationstechnologie.Der pragmatische Nutzen der Zahlentheorie liegt sowohl in der Codierung – womit Datenübertragung nicht nur möglich, sondern auch kompakt, schnell und fehlerfrei gemacht wird – wie auch in der Chiffrierung – also bei der Bereitstellung der Verschlüsselungsverfahren, mit denen die zunehmenden Sicherheitsbedürfnisse der Datenkommunikation gelöst werden.Eines der verbreitetsten Verschlüsselungsverfahren des Internets basiert auf der folgenden, verblüffend einfachen Feststellung: Es ist einerseits ungemein einfach, zwei relativ große Primzahlen, sagen wir: p und q, zu finden und miteinander zu multiplizieren, also n = p mal q. Aber es ist andererseits sehr schwer, aus dem Produkt n wieder die Faktoren p und q zu gewinnen. Da das auf dieser Tatsache aufgebaute Verschlüsselungsverfahren sehr weit verbreitet ist, bleibt es nicht aus, dass jedes Mal, wenn eine neue Entdeckung über Primzahlen öffentlich wird, der Verdacht aufkommt, dies könnte dramatische Auswirkungen auf die Kryptografie und somit auf unsere Sicherheit haben.Im Jahr 2002 wurde von dem indischen Computerwissenschaftler Agrawal und seinen Studenten Kayal und Saxena eine solche Entdeckung gemacht: Sie fanden den sogenannten polynomial-deterministischen Algorithmus für die Primheit allgemeiner Zahlen. Die drei lösten damit auf wunderbar elegante Weise ein Problem der Komplexitätstheorie, über das sich seit gut zwei Jahrzehnten manche der besten Fachleute den Kopf zerbrochen hatten. Ihre Lösung – die kurzerhand mit dem Akronym „AKS-Algorithmus“ benannt wurde – hat alles von einem kleinen Wunder.Auch das Problem, das sie mit diesem Algorithmus lösten, hat ein kurzes Etikett im Jargon der Komplexitätstheorie: „Primes is in P“. Und so hieß auch der Titel ihres Manuskripts. „Primes is in P“ bezeichnet die Behauptung, dass eine Rechenmethode existiert, mit der sich die Frage, ob eine beliebige Zahl eine Primzahl ist oder nicht, mit nur „polynomial“ vielen Rechenschritten beantworten lässt: „Primheit liegt im Bereich polynomialer Berechenbarkeit“. Und genau das haben die drei Autoren bewiesen.Für den Beweis haben die drei abseits vom Hauptstrom der bisherigen Forschung eine fundamental neue Idee ins Spiel gebracht. Alle früheren Versuche hatten sich nur durch zunehmende Komplikation der verwendeten mathematischen Methoden dem Beweisziel angenähert, ohne es jedoch zu erreichen. Demgegenüber erscheint die neue Idee von Agrawal und seinen Mitarbeitern völlig überraschend, aber trotzdem — im Nachhinein betrachtet ­— auf leicht verständliche Weise zum Ziel zu führen.Eleganz, Einfachheit und Originalität zusammen tragen, verstärkt durch den Überraschungseffekt, zu einem einmaligen mathematischen Schönheitserlebnis bei. Das wird in der Fachwelt entsprechend goutiert und auch honoriert: Die drei Autoren wurden sogleich ans renommierte Princeton Institute for Advanced Studies eingeladen, und ihr Ergebnis wurde zwei Jahre später in den Mathematical Annals veröffentlicht, dem mathematischen Journal, das nur die besten Ergebnisse des Jahres aus sämtlichen Teildisziplinen der Mathematik druckt. So viel zur Schönheit.Da Primzahlen so innig mit unseren Sicherheitsinteressen (und dem geliebten Geld!) verbandelt sind, stellt sich aber auch die pragmatische Frage: Welche praktische Auswirkung kann diese Entdeckung für die Kryptografie haben? Obwohl, um es gleich zu sagen, die eindeutige Antwort „keine unmittelbare Auswirkung“ heißt, darf die Frage keineswegs als naiv abgetan werden. Schon deswegen nicht, weil sie mit zu den Gründen zählt, die das American Institute for Mathematics angab, um gleich nach der Entdeckung eine einwöchige Tagung zum Thema „AKS-Algorithmus“ zu organisieren. Ich möchte im Rest dieses Artikels erklären, wie diese (beruhigende!) Antwort zu verstehen ist.Eine denkbare Anwendung des AKS-Algorithmus könnte sein, die Primheit von Zahlen zu beweisen, die vorher rechnerisch nicht bewiesen werden konnte. Lässt sich damit eine auf Primzahlen gegründete Verschlüsselung knacken? Nun, die Primzahlen, die in der Kryptografie verwendet werden, sind einige wenige Hundert Dezimalstellen groß – gigantisch für das mensch­liche Rechenvermögen, aber recht klein für die Beweisalgorithmen, die es bereits vor AKS gab. Vor allem ist aber die Krypto­grafie gar nicht auf einen vollständigen Beweis angewiesen; es genügt durch einfachere und schnellere Verfahren nachzuweisen, dass die verwendeten Zahlen mit überwältigender Wahrscheinlichkeit prim sind.Wunder brauchen längerUnd so wird es auch gemacht: Die Wahrscheinlichkeit, dass die bisher schon verwendeten Verfahren eine zusammengesetzte Zahl fälschlich als prim erklären, ist kleiner etwa als beispielsweise diejenige, unter allen Atomen des Universums genau ein einziges Atom wiederzufinden. Die Praktiker der Kryptografie haben somit schon lange eine gute Lösung für ihr Problem und brauchten nicht auf „Primes is in P“ zu warten. Und sollten sie sogar einen echten – also nicht probabilistischen – Beweis wünschen, so hatten sie auch schon vorher Verfahren zur Verfügung, die das konnten; nur waren bisher die erzeugten Primzahlen nicht absolut zufällig. Einem Ozean Zufälligkeit wird ein Wermuttropfen Notwendigkeit – sprich Gesetzmäßigkeit – beigemischt.Was sich die Mathematiker in der Komplexitätstheorie wünschten, ist jedoch verschieden von den Problemen der angewandten Kryptografie: Für eine beliebig vorgegebene Zahl sollte die Primheit bewiesen werden, und da ist auch der kleinste Wermuttropfen nicht erlaubt! Nur hierzu ist es nötig, dass der Beweis der Primheit deterministisch und polynomial ist. Letzteres bedeutet, dass bei Zahlen von beliebiger Länge m der Beweis nicht mehr als m-hoch-k-Rechenschritte beanspruchen darf, wobei k eine feste Kon­stante ist, die insbesondere unabhängig von m ist. Dass k fest bleibt auch wenn m gegen Unendlich strebt, ist eine wesentliche Bedingung; erst sie verleiht dem Algorithmus das begehrte Attribut „is in P“.Deterministische Algorithmen, die die Primheit von Zahlen von mehreren 1.000 bis vielleicht 10.000 Dezimalstellen praktisch beweisen können, waren auch schon vorher bekannt. Nur war dabei der Exponent k in der obigen Aufwandabschätzung keine Konstante, sondern eine langsam mit m gegen Unendlich wachsende Funktion, die zwar für m = 108 immer noch kleiner als 3 ist, aber eben nicht konstant. Damit konnten sich die Mathematiker natürlich nicht zufriedengeben, bis der AKS-Algorithmus gefunden wurde, der die erwünschten Eigenschaften hat und dazu noch, wie gesagt, von verblüffender Einfachheit und Eleganz ist.Man darf nicht überrascht sein, dass sich nach diesem Durchbruch gleich ein neuer Wunsch eingestellt hat: Den AKS-Algorithmus so zu verbessern, damit er auch praktisch die schnellsten Ergebnisse liefert. Zurzeit lässt sich sagen, dass AKS erst für gigantische Zahlen von mehreren Milliarden Stellen schneller ist als die bekannten Algorithmen. Für Verbesserungen scheinen recht harte Widerstände im Weg zu stehen, ausgeschlossen ist es aber nicht. Bis heute, sieben Jahre nach der Entdeckung von AKS, wurde noch keine gefunden.Aber man könnte noch eine andere Sorge in Bezug auf die Sicherheit kryptografischer Verfahren haben: Auf den rechnerischen Aufwand, große Zahlen in Primzahlen zu zerlegen und so Verschlüsselungen zu knacken, hat AKS, wie gesagt, keine direkte Auswirkungen. Aber es ist eine Tatsache, dass die Entdeckung des AKS-Algorithmus unerwartet wie ein Wunder bekannt gegeben wurde. Da könnte man auf die Idee kommen, dass ein anderes neues Wun­der zu einer sicherheitskritischen Entdeckung über die Faktorisierung von Primzahlen führen wird.Aber über die Wahrscheinlichkeit von Wundern lässt sich mathematisch nichts Genaues sagen ­— darüber sind sich ausnahmsweise alle Fachleute einig. Mit diesem Argument bewaffnet kann man nur, an Bob Dylan angelehnt, das Lied singen: „The moral of the story / Is that one should never be / Where wonders don’t belong“.