Primzahlen & Faktorisierung

Der vielleicht älteste und schönste Beweis der Mathematik steht in Buch IX, Proposition 20 der Elemente des Euklid, entstanden um 300 v. Chr.: Es gibt unendlich viele Primzahlen. Der Gedanke: Man nehme irgendeine endliche Liste von Primzahlen, multipliziere sie alle und addiere 1 — das Ergebnis ist entweder selbst eine neue Primzahl oder besitzt einen Primfaktor, der in der Liste fehlt. Die Liste war also unvollständig. Warum das Gewicht hat: Die Primzahlen sind die multiplikativen Atome der Arithmetik — jede ganze Zahl entsteht, indem man Primzahlen multipliziert, und Euklid hatte soeben gezeigt, dass der Vorrat an Atomen nie zur Neige geht. Sein direkter Beweis ist von solcher Klarheit, dass er bis heute unverändert in jedem Lehrbuch steht; er kommt ohne Symbole und ohne Rechnung aus und braucht nur die Gewissheit, dass jede endliche Liste sich übertreffen lässt. Dreiundzwanzig Jahrhunderte lang nachgedruckt, übersetzt und bewundert, trägt der Satz noch immer das Fundament, auf dem die gesamte moderne Zahlentheorie steht.

Primzahlen sind die multiplikativen Atome der ganzen Zahlen. Der Fundamentalsatz der Arithmetik besagt, dass jede ganze Zahl größer als eins auf genau eine Weise in Primfaktoren zerfällt — 60 = 2²·3·5, und anders geht es nicht. Die Primzahlen bilden damit das Periodensystem der natürlichen Zahlen, und die tiefen Fragen der Zahlentheorie laufen in aller Regel auf Fragen über Primzahlen hinaus. Ihren Sinn beziehen diese Atome aus der Eindeutigkeit: Wer einen Faktor austauscht, hat eine andere Zahl vor sich; und dass zwei Zahlen durch dasselbe teilbar sind, liegt an einem gemeinsamen Primfaktor. Die ersten Glieder der Reihe — 2, 3, 5, 7, 11, 13 — wirken beinahe unscheinbar. Nur: Keine Formel bringt sie hervor. Es bleibt das Sieb des Eratosthenes mit seinen Nachfahren — Vielfache ausstreichen, bis nur die Überlebenden stehen.

Ein erkennbares Muster haben die Primzahlen nicht, zufällig verteilt sind sie trotzdem nicht. Ihr Ausdünnen gehorcht einem Gesetz: Nach dem Primzahlsatz, den Hadamard und de la Vallée Poussin 1896 bewiesen, liegt die Anzahl der Primzahlen unterhalb von N asymptotisch bei N / ln N — in der Nähe einer großen Zahl N trifft man also im Mittel etwa alle ln N Schritte auf eine Primzahl. Die Schwankungen im Kleinen dagegen bleiben rätselhaft. Die Riemannsche Vermutung von 1859 behauptet, dass sämtliche nichttrivialen Nullstellen der Zetafunktion auf einer einzigen senkrechten Geraden der komplexen Ebene liegen; träfe sie zu, ergäbe sich daraus die schärfstmögliche Fehlerschranke für die Primzahlfunktion. Sie gehört zu den Clay-Millennium-Problemen, und um sie herum hat sich ein langer Katalog verwandter Vermutungen angesammelt — Primzahlzwillinge, Goldbach, Polignac.

Mehr als eine Angelegenheit für Kenner ist das alles, weil das Faktorisierungsproblem — finde zu einer großen ganzen Zahl ihre Primfaktoren — weithin als rechnerisch schwer gilt. Zwei Primzahlen zu multiplizieren kostet nichts; sie aus dem Produkt zurückzugewinnen, offenbar sehr viel. Ein klassischer Algorithmus mit polynomieller Laufzeit ist nicht bekannt; das Zahlkörpersieb läuft subexponentiell und versagt bei Zahlen von einigen tausend Bit. Auf der Kluft zwischen leichtem Multiplizieren und schwerem Faktorisieren ruhen die RSA-Verschlüsselung und mit ihr der größte Teil der Public-Key-Kryptographie — einer Kluft, die mit P gegen NP und mit den Quantenrechnern verflochten ist.