Primzahltest

Der Primzahltest sagt Ihnen, ob eine ganze Zahl eine Primzahl ist, und zeigt – anders als die meisten Online-Rechner – den echten Algorithmus, der es bewiesen hat, nicht etwa eine zwischengespeicherte Nachschlagetabelle. Geben Sie eine beliebige ganze Zahl ein, positiv oder negativ, klein oder riesig, und das Werkzeug entscheidet anhand ihrer Größe, welcher echte Algorithmus ausgeführt wird.

Für Zahlen unter 10¹² (einer Billion) wird echte Probedivision durchgeführt: Bei 2 beginnend wird jede ganze Zahl bis zur Ganzzahl von √n als möglicher Teiler getestet. Die Prüfung endet, sobald ein Teiler gefunden wird (zusammengesetzt), oder bestätigt die Primalität, wenn kein einziger Teiler gefunden wurde. Bei sehr vielen Kandidaten zeigt das Protokoll die ersten ~18 getesteten sowie den letzten an, mit einem ehrlichen Hinweis, wie viele in der Darstellung übersprungen wurden – aber tatsächlich wird jeder einzelne Kandidat vom Code geprüft, keiner wird bei der Berechnung übersprungen.

Für Zahlen ab dieser Schwelle – der Größenordnung, die in der Kryptografie verwendet wird – würde die Probedivision viel zu lange dauern. Daher schaltet das Werkzeug auf den Miller–Rabin-Primzahltest um, mit einem festen, deterministischen Satz von 13 Primzahlen als Zeugen (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Für genau diesen Zeugensatz ist ein bekanntes Ergebnis belegt: Er produziert keine falschen Primzahlen für jedes n unterhalb von 3.317.044.064.679.887.385.961.981 (etwa 3,3 × 10²⁴), eine Grenze, die durch rechnerische Überprüfung festgestellt wurde (siehe Sorenson & Webster, 2015, und die weithin bekannte Tabelle deterministischer Zeugen, zu der dieses Ergebnis gehört). Oberhalb dieser Grenze wird der Test ebenfalls ausgeführt, aber das Werkzeug informiert Sie ehrlich, dass die Garantie dann zu einer extrem starken probabilistischen Aussage wird, nicht mehr zu einer mathematischen Gewissheit.

Das Miller–Rabin-Protokoll schreibt n − 1 = 2ˢ × d mit ungeradem d, durchläuft dann die echte modulare BigInt-Exponentiation – Quadrieren und Multiplizieren, modulo n in jedem einzelnen Schritt reduziert, damit die Zahlen niemals explodieren – Bit für Bit für den ersten Zeugen, und meldet das Ergebnis jedes Zeugen, einschließlich dessen, welcher Zeuge die Zusammengesetztheit beweist, falls die Zahl keine Primzahl ist. Alles läuft lokal in Ihrem Browser: kein Server, keine externe API, keine Daten verlassen jemals Ihr Gerät.