Große Primzahlen

Seit einigen Tagen gibt es eine neue größte bekannte Primzahl. Die Details der Entdeckung können hier nachgelesen werden. Nach solchen medienwirksamen mathematischen Fortschritten tut sich in den Onlineforen häufig die Frage auf, „wozu so etwas gut sein soll“. Das möchte ich zum Anlass nehmen, um sie mit einem schon länger angekündigten Artikel über meine Dissertation zu beantworten, die ich in wenigen Wochen verteidigen werde. Ich werde die Anwendungsbereiche großer Primzahlen erklären und den damit zusammenhängenden praktischen Nutzen von mathematischen Tests, deren Aufgabe in der Klärung der Frage liegt, ob eine gegebene Zahl prim ist oder nicht.

Eine Primzahl ist eine natürliche Zahl ungleich 1, die nur durch sich selbst und durch 1 teilbar ist. 2, 3, 5, 7 und 11 sind die ersten fünf Primzahlen. 4 ist keine Primzahl, denn 4 ist nicht nur durch 1 und 4, sondern auch durch 2 teilbar. 6 ist durch 2 und durch 3 teilbar und somit ebenfalls keine Primzahl. Es gelten:

1. Jede natürliche Zahl ungleich 1 kann als Produkt von Primzahlen geschrieben werden. (Z.B.: 6=2*3, 35=5*7, 12=2*2*3, 5=5, 8=2*2*2, 29=29, 30=2*3*5)
2. Es gibt unendlich viele Primzahlen. (Interessierte finden hier einen Beweis dieser Aussage.)

Wir beschäftigen uns im Folgenden hauptsächlich mit der ersten Aussage. Die Schreibweise einer natürlichen Zahl als Produkt von Primzahlen nennt man Primfaktorzerlegung. 2*3*5 ist also die Primfaktorzerlegung von 30, und die Zahlen 2, 3 und 5 sind ihre Primfaktoren. 11 ist der einzige Primfaktor von 11. Folgendes Problem stand im Zentrum meiner Dissertation:

Sei eine beliebige natürliche Zahl gegeben. Berechne ihre Primfaktorzerlegung.

Dies ist das sogenannte Faktorisierungsproblem natürlicher Zahlen. Für kleine Zahlen ist es recht einfach zu lösen. Jedes Volksschulkind kennt die Primfaktoren von 15. Die Primfaktorzerlegung der Zahl 1023 ist gewiss schwieriger zu finden, aber für gute Kopfrechner ebenfalls keine große Herausforderung. Selbst diese werden allerdings an ihre Grenzen stoßen, wenn sie die Primfaktoren von 12495577 berechnen sollen; ein Computer hingegen gibt in Sekundenbruchteilen 2311 und 5407 aus. Wie aber lauten die Primfaktoren von
17969491597941066732916128449573246156367561808012600070888918835531
72646034149093349337224786865075523085586419992922181443668472287405
20652579374956943483892631711525225256544109808191706117425097024407
18010364831638288518852689 ?
Diese riesige Zahl war eine der Aufgaben der RSA Factoring Challenge, die 1991 begann und 2007 endete. Dabei handelte es sich um eine Tabelle von Zahlen, für deren Faktorisierung teils Preisgelder bis zur Höhe von $200.000 ausgelobt wurden. Bis heute ist es niemandem gelungen, die Primfaktorzerlegung der obigen Zahl zu finden. Ähnlich verhält es sich mit einem Großteil der anderen Zahlen aus der Challenge.
Selbst mit den besten bekannten Algorithmen auf den schnellsten Computern der Welt ist das Faktorisierungsproblem für große Zahlen von bestimmter Form unheimlich schwer zu lösen. Ganz besonders schwierig gestaltet sich die Zerlegung, wenn wir es mit einem Produkt von zwei ebenfalls sehr großen Primzahlen zu tun haben. Alle Zahlen der RSA Challenge haben eine solche Form N=p*q, wobei p und q groß und prim sind.

Damit ist das Problem erklärt. Welchen konkreten Nutzen aber hat die Spielerei mit großen Primzahlen? Tatsächlich kann man ohne Übertreibung sagen, dass von diesen die Privatsphäre und die Sicherheit der meisten Transaktionen im Internet abhängt. Sie haben vielfältigste Anwendungen in der Kryptographie, von denen ich im Folgenden nur eine grob beschreiben möchte. Es handelt sich dabei um das Verschlüsselungssystem RSA, das sich die oben beschriebene Schwierigkeit des Faktorisierungsproblems zunutze macht. Für RSA werden zunächst zwei große  Primzahlen p und q gesucht, die bestimmte Eigenschaften erfüllen. Damit diese Suche möglichst rasch und effizient vonstatten geht, werden verschiedenste Tests und Algorithmen verwendet; ähnlich wie jener, mit dem neulich auch die neueste größte bekannte Primzahl entdeckt wurde. Hat man p und q gefunden, so werden die beiden Primzahlen miteinander multipliziert und man erhält N=p*q. An dieser Stelle ist es wichtig, p und q zu löschen. Deren Produkt, die Zahl N, kann öffentlich gemacht werden. Die Funktionsweise von RSA, welche ich hier nicht mehr genauer erläutern kann, erlaubt eine effiziente und sichere Kommunikation. Die Sicherheit des Kommunikationskanals hängt allerdings davon ab, dass es praktisch unmöglich ist, aus der öffentlichen und für jeden einsehbaren Zahl N die beiden Primfaktoren p und q zu berechnen.
Ich habe in meiner Dissertation einen kryptoanalytischen Ansatz verfolgt und mich dabei an die schwierige Aufgabe gewagt, bessere Algorithmen für das Faktorisierungsproblem zu finden. Auch wenn mein Fortschritt keine Gefahr für die Sicherheit von RSA darstellt, ist mir die Entwicklung eines neuen Verfahrens gelungen, das effizienter faktorisiert als die mit meinem Algorithmus vergleichbaren Methoden. Außerdem habe ich mich mit Beziehungen zwischen dem Faktorisierungsproblem und anderen Herausforderungen aus dem Bereich der algorithmischen Zahlentheorie beschäftigt. Wer Lust auf einen kurzen Blick in meine Arbeiten hat, wird hier fündig.

Wozu also soll es gut sein, sich mit der Suche nach einer neuen größten bekannten Primzahl zu beschäftigen? Zum einen treibt diese Suche die Entwicklung von besseren Tests zur Primzahlerkennung voran. Sie befördert auch die Forschung an möglichst effizienter Programmierung dieser Algorithmen und der Verteilung der Rechenlast in einem Computernetzwerk. All das hat einen konkreten praktischen Nutzen, den ich in diesem Beitrag beschrieben habe. Zum anderen gibt es auch Leute, die einfach Spaß an der Sache haben. Viele Hobbymathematiker stellen freiwillig die Rechenleistung ihres Computers zur Verfügung.
Ich möchte dem noch hinzufügen, dass die Frage nach dem direkten Nutzen in der Mathematik generell kein Kriterium für Förderungswürdigkeit von Forschung sein darf. Daraus würde sich nämlich eine immense Beschneidung des wissenschaftlichen Fortschritts ergeben. Die Erfahrung zeigt außerdem, dass sich konkrete Anwendungsmöglichkeiten von Erkenntnissen manchmal erst lange Zeit nach ihrer Entdeckung ergeben.

Liebe Grüße
Markus Hittmeir