Dies ist eine maschinelle Übersetzung; die englische Fassung ist das Original. Original lesen
Primzahlen dünnen mit einer benennbaren Rate aus
In der Nähe einer 1024-Bit-Zahl ist etwa jede 355-te ungerade Zahl eine Primzahl. Das ist keine kleine Wahrscheinlichkeit – und der einzige Grund, warum Public-Key-Kryptographie möglich ist.
Es gibt 25 Primzahlen unter 100, 168 unter 1000 und 78.498 unter einer Million. Die Anzahlen nehmen ab, aber sie hören nie auf, und die Rate, mit der sie ausdünnen, gehört zu den nützlichsten Erkenntnissen der Mathematik.
Eine von ln n
In der Nähe einer Zahl n ist etwa eine von ln n Zahlen eine Primzahl. Unter 100 sagt dies 100 / ln 100 = 21,7 Primzahlen voraus, und Prime Sieve gibt genau dies neben der tatsächlichen Anzahl von 25 aus, zusammen mit dem Fehler von 13,1 %.
Die Schätzung ist an dieser Stelle grob und verbessert sich. Bei einer Million liefert N / ln N den Wert 72.382 gegenüber den tatsächlichen 78.498, was einem Fehler von 7,8 % entspricht. Der relative Fehler schrumpft mit wachsendem N – genau das ist der eigentliche Inhalt des Primzahlsatzes.
Die bessere Schätzung, die schlechter aussieht
Das Werkzeug gibt eine zweite Näherung aus, Li(N), den Integrallogarithmus. Bei N = 100 liefert er 29,1 und ist damit schlechter als die grobe Schätzung: ein Fehler von 16,3 % gegenüber 13,1 %.
Wer nur diese Zeile liest, würde schließen, dass sich die aufwendigere Formel nicht lohnt. Ändert man N, kehrt sich die Rangfolge um und schlägt nie wieder zurück:
- N = 100: N/lnN weicht um 13,1 % ab, Li um 16,3 %
- N = 1000: N/lnN weicht um 13,8 % ab, Li um 5,1 %
- N = 10⁶: N/lnN weicht um 7,8 % ab, Li um 0,16 %
Li ist weniger eine Verfeinerung von N / ln N als vielmehr die ehrliche Variante davon. Die grobe Formel wendet die Dichte bei n auf den gesamten Bereich von 0 bis n an, obwohl die Dichte nahe 2 ganz anders ist als die Dichte nahe einer Million. Li integriert 1/ln t über den gesamten Bereich, anstatt sie als konstant anzunehmen, und der Lohn ist ein Fehler von eins zu sechshundert, wo die Abkürzung noch um 8 % falsch liegt.
Eine einzelne Auswertung einer Näherung sagt nichts darüber aus, ob sie gut ist. Man benötigt ihr Verhalten bei wachsender Eingabe.
Warum sie niemals ausgehen
Weil 1/ln n langsam fällt. Ihre Summe divergiert, sodass die Primzahlen zwar spärlich sind, aber nicht spärlich genug, um endlich zu sein.
Euklids Beweis ist direkter und älter. Man nehme eine beliebige endliche Liste von Primzahlen, multipliziere sie miteinander und addiere eins. Das Ergebnis lässt bei der Division durch jede Primzahl auf der Liste den Rest 1, sodass seine Primfaktoren alle auf der Liste fehlen. Keine endliche Liste kann vollständig sein.
Die beiden anderen Anzeigen des Werkzeugs weisen darauf hin, wie vieles noch offen ist. Es zählt 8 Primzahlzwillinge unter 100 und gibt die größte Lücke mit 8 an. Ob sich die Primzahlzwillinge unendlich fortsetzen, ist unbewiesen – ebenso wie die Vermutung, dass zwischen zwei aufeinanderfolgenden Quadratzahlen stets eine Primzahl liegt.
Die Zahl, die die Schlüsselgröße bestimmt
Das Erzeugen eines RSA-Schlüssels bedeutet, große Primzahlen zu finden, und das Verfahren besteht darin, eine zufällige ungerade Zahl der passenden Größe zu wählen und sie zu testen.
Wie lange das dauert, ist genau die Frage nach der Dichte. Eine 1024-Bit-Zahl liegt nahe 2¹⁰²⁴, und ln(2¹⁰²⁴) = 1024 × ln 2 = 710. In dieser Gegend ist also etwa eine von 710 Zahlen eine Primzahl, und da man nur ungerade Kandidaten testet, eine von 355.
Dreihundertfünfundfünfzig Versuche, jeder davon ein schneller probabilistischer Primzahltest. Aus diesem Grund dauert die Schlüsselerzeugung einen Moment und nicht Zeitalter, und der gesamte Aufwand ergibt sich aus einem Logarithmus. Erhöht man den Exponenten, wächst der Aufwand linear mit der Bitlänge, weshalb 2048-Bit- und 4096-Bit-Schlüssel praktisch bleiben.
Hätten sich die Primzahlen auch nur geringfügig schneller ausgedünnt, etwa wie 1/n, wäre die Suche aussichtslos und das Internet auf etwas anderem aufgebaut.
Niemand beweist die Primzahlen, die er verwendet
Ein Detail macht die 355 Versuche günstig: Der Test weist die Primzahleigenschaft nicht nach.
Der Miller-Rabin-Test wählt einen zufälligen Zeugen und stellt eine Frage, die jede Primzahl auf dieselbe Weise beantwortet. Eine zusammengesetzte Zahl kann wie eine Primzahl antworten, aber höchstens ein Viertel der möglichen Zeugen lässt dies zu. Jede unabhängige Runde verringert die Wahrscheinlichkeit, getäuscht zu werden, somit um mindestens das Vierfache. Vierzig Runden hinterlassen einen Worst-Case unter 4⁻⁴⁰, was etwa 10⁻²⁴ entspricht.
Das liegt weit unter der Wahrscheinlichkeit eines unerkannten Speicherfehlers im Rechner, der die Arithmetik ausführt. Die Schlüssel, die den weltweiten Datenverkehr schützen, beruhen auf Zahlen, die fast sicher Primzahlen sind, und der verbleibende Zweifel ist kleiner als jener der Hardware.