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. 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.
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 —, 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. 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.
Die Kryptographie steht und fällt mit der Primzahl-Arithmetik, und am Horizont steht der Quantencomputer: Shors Algorithmus (1994) faktorisiert ganze Zahlen auf einer hinreichend großen Quantenmaschine in polynomieller Zeit, weshalb NIST seit 2016 Post-Quanten-Verfahren standardisiert — gitterbasiert, hashbasiert — und Unternehmen mitten in der Umstellung stecken. Auch außerhalb der Kryptographie tragen Primzahlen den Apparat: Hashtabellen (Primzahl-Moduli verteilen Kollisionen), randomisiertes Fingerprinting, probabilistische Primzahltests bei der Schlüsselerzeugung. Die Riemannsche Vermutung bleibt das berühmteste ungelöste Problem der Mathematik; ein Beweis würde tausend nachgeordnete Vermutungen klären und sichtbar machen, wie sicher die kryptographischen Konstruktionen auf Primzahlen tatsächlich stehen.