3. Primzahl-Spielwiese
Fermat’sche Primzahlen
Pierre de Fermat (1607-1665) hat entdeckt, dass diese vier Zahlen Primzahlen sind. Er vermutete, dass alle Zahlen dieser Form Primzahlen seien. Tatsächlich ist es aber eher umgekehrt: Leonhard Euler hat fast ein Jahrhundert später gezeigt, dass die fünfte Fermat-Zahl keine Primzahl ist.
Was ohne geeignete Rechenmaschinen hundert Jahre dauerte, können Sie in Sekundenbruchteilen nachholen, wenn Sie in der letzten Zeile die 4 in 5 ändern und nochmal auf „Ausführen“ klicken.
Heute vermutet man, dass es keine weitere Fermat’sche Primzahl gibt. Für den Fall, dass Sie noch weiter testen wollen, hier eine Variante für BigInt-Zahlen, bei der Sie ziemlich weit nach rechts scrollen müssen:
Sicher werden Sie sich fragen, wie man bei derart große Zahlen (die letzte ist immerhin 1234-stellig) prüfen kann, ob sie Primzahlen sind.
Eine naive Methode wäre, der Reihe nach alle Zahlen auf Teilbarkeit zu prüfen. Von 2 bis zu unserer 1234-stelligen Zahl n? Das ist nicht nötig: Zu jedem Teiler a von n gibt es ja auch den Ergänzungsfaktor b, so dass ab=n. Einer der beiden muss \le \sqrt n sein. Wenn wir also bis zur 617-stelligen Zahl \sqrt n keinen Teiler gefunden haben, ist n eine Primzahl. Natürlich ist hier auch mit dieser „Wurzeloptimierung“ nicht viel gewonnen. Hätten wir einen schnellen Computer damit beim Urknall gestartet, wäre er heute vielleicht bei einer 25-stelligen Zahl angekommen. Bis zur ersten 26-stelligen Zahl wären es dann noch hundert Milliarden Jahre. So ließe die 617-stellige Zahl noch etwas auf sich warten. Der rasante Primzahltest, mit dem die mathGUIde-Funktion isPrime arbeitet – der Miller-Rabin-Test –, ist tatsächlich kein mathematisch sicherer Test, sondern hat eine Fehlerwahrscheinlichkeit, die man aber so klein halten kann, dass sie in der Praxis vernachlässigbar ist.
Mersenne’sche Primzahlen
Fermats älterer Zeitgenosse Marin Mersenne (1588–1648) hat eine andere Formel aufgestellt, von der er glaubte, sie liefere nur Primzahlen:
Primzahlzwillinge
Mehr zu den Primzahlzwillingen
Die Goldbach’sche Vermutung
Die Goldbachsche Vermutung: Jede gerade Zahl ab 4 ist als Summe zweier Primzahlen darstellbar. (Christian Goldbach : 1690–1764)
Wenn Sie diese Tabelle Ihren Glauben nährt, dass die Goldbach’sche Vermutung richtig ist, werden so gut wie alle Mathematiker auf Ihrer Seite sein. Aber Glauben ist nicht Wissen: Bisher ist kein Beweis dafür gefunden worden.
Der RSA-Algorithmus
Dieser Abschnitt ist noch unfertig.
Die folgenden Anweisungen erzeugen zwei zufällige 50-stellige Primzahlen und ermitteln ihr Produkt.
Wenn Sie versuchen, dieses Produkt mit der Funktion factor wieder in p und q zu zerlegen, werden Sie die Antwort des Browser-Tab nicht erleben. Das liegt nur zum Teil daran, dass factor nicht sehr effizient ist. Auch die besten Faktorisierungsprogramme scheitern an Produkten zweier großer Primzahlen (ab etwa je 300 Dezimalstellen).
Die Asymmetrie zwischen dem Erzeugen und dem Faktorisieren großer Primzahlprodukte ist die Grundlage für das RSA-Kryptosystem. Es folgt ein Beispiel mit der mathGUIde-Klasse Rsa:
Beachten Sie bitte, dass JavaScript nicht für praktische Kryptografie geeignet ist, weil die Rechenzeit von Multiplikationen Schlüsse auf die Größenordnung der Faktoren zulässt.
