Primzahlen & Faktorisierung

In Buch IX, Proposition 20 der Elemente Euklids (~*300 v. Chr.*) steht einer der ältesten und schönsten Beweise der Mathematik: es gibt unendlich viele Primzahlen. Nehmen wir endlich viele an; multipliziere sie alle; addiere 1; das Ergebnis ist entweder selbst eine neue Primzahl oder hat einen Primfaktor, der nicht in der Liste steht — Widerspruch, so oder so. Das Argument wiegt schwer, weil die Primzahlen die multiplikativen Atome der Arithmetik sind — jede ganze Zahl entsteht durch ihr Multiplizieren, und Euklid hatte eben gezeigt, dass dieser Vorrat an Atomen niemals versiegt. Die Schlussweise ist ein Widerspruchsbeweis von solcher Klarheit, dass sie in jedem modernen Lehrbuch unverändert weiterlebt — sie braucht weder Symbole noch Rechnung, nur die Gewissheit, dass sich eine endliche Liste stets überholen lässt. Seit dreiundzwanzig Jahrhunderten wird er nachgedruckt, übersetzt und bestaunt, und sein Satz trägt bis heute die gesamte moderne Zahlentheorie.

Primzahlen sind die multiplikativen Atome der ganzen Zahlen. Der Fundamentalsatz der Arithmetik sagt: jede ganze Zahl oberhalb der Eins zerfällt eindeutig in Primfaktoren — 60 = 2²·3·5, und keinen zweiten Weg gibt es —, womit die Primzahlen zum Periodensystem der natürlichen Zahlen werden; tiefe Fragen der Zahlentheorie laufen am Ende auf Fragen über sie hinaus. Erst die Eindeutigkeit verleiht den Atomen ihren Sinn: ändert man einen Faktor, ändert man die Zahl, und ein gemeinsamer Primfaktor ist es, der zwei Zahlen durch dasselbe teilbar macht. Die ersten Primzahlen — 2, 3, 5, 7, 11, 13 — wirken fast gewöhnlich; die Schwierigkeit liegt darin, dass keine Formel sie erzeugt, sondern allein das Sieb des Eratosthenes und seine Nachfahren, die Vielfache ausstreichen, bis die Überlebenden bleiben.

Die Primzahlen verteilen sich nach keinem sichtbaren Muster und sind doch nicht zufällig. Sie dünnen sich vorhersehbar aus — der Primzahlsatz (Hadamard, de la Vallée Poussin, 1896) zeigt, dass die Anzahl der Primzahlen unterhalb N asymptotisch N / ln N beträgt, sodass Primzahlen nahe einer großen Zahl N etwa alle ln N Schritte auftauchen —, die lokalen Schwankungen aber bleiben rätselhaft. Die Riemannsche Vermutung (Riemann, 1859) behauptet, alle nichttrivialen Nullstellen der Zeta-Funktion lägen auf einer einzigen senkrechten Geraden in der komplexen Ebene; wäre sie wahr, lieferte sie die engstmögliche Fehlerschranke für die Primzahlfunktion. RH ist eines der Clay-Millennium-Probleme, und um sie herum gruppiert sich ein langer Katalog verwandter Vermutungen — Primzahlzwillinge, Goldbach, Polignac.

Was die Sache zu mehr als einer Liebhaberei macht: das Faktorisierungsproblem — finde zu einer großen ganzen Zahl ihre Primfaktoren — gilt weithin als rechnerisch schwer. Zwei Primzahlen zu multiplizieren ist trivial; sie aus dem Produkt zurückzugewinnen ist es nicht. Ein klassischer Algorithmus mit polynomieller Laufzeit ist nicht bekannt; das Zahlkörpersieb läuft subexponentiell und wird auf Zahlen mit ein paar tausend Bit untauglich. Die RSA-Verschlüsselung und der größte Teil der Public-Key-Kryptographie stehen und fallen mit dieser Kluft zwischen Multiplizieren (leicht) und Faktorisieren (offenbar schwer) — einer Kluft, die mit P-gegen-NP und mit Quantenrechnern verflochten ist.