Primzahlprüfer

Der Primalitätsprüfer sagt Ihnen, ob eine ganze Zahl eine Primzahl ist, und zeigt Ihnen – anders als die meisten Online-Rechner – den tatsächlichen Algorithmus, der dies bewiesen hat, und keine zwischengespeicherte Nachschlagetabelle. Geben Sie eine beliebige Ganzzahl ein, positiv oder negativ, klein oder riesig, und das Tool entscheidet anhand seiner Größe, welcher reale Algorithmus ausgeführt werden soll.

Für Zahlen unter 10¹² (eine Billion) führt es eine echte Probedivision durch: Beginnend bei 2 versucht es jeden ganzzahligen Kandidaten bis zur Untergrenze von √n als möglichen Teiler, stoppt den Moment, in dem gleichmäßig dividiert wird (zusammengesetzt), oder bestätigt, dass dies nicht der Fall ist, sobald jeder Kandidat bis zu √n überprüft wurde (Primzahl). Bei einer großen Anzahl von Kandidaten wird die angezeigte Spur auf die ersten ca. 18 Versuche plus den letzten begrenzt, mit einem ehrlichen Hinweis darauf, wie viele in der Anzeige übersprungen wurden – aber jeder einzelne Kandidat wird immer noch tatsächlich vom Code überprüft, keiner wird bei der Berechnung übersprungen.

Für Zahlen an oder über diesem Schwellenwert – dem Größenbereich, der in der Kryptographie verwendet wird – würde die Versuchsteilung zu lange dauern, daher wechselt das Tool zum Miller-Rabin-Primalitätstest mit einem festen, deterministischen Satz von 13 Hauptzeugen (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Dieser exakte Zeugensatz ist ein bekanntes Ergebnis: Er weist keine falsch positiven Ergebnisse für n unter 3.317.044.064.679.887.385.961.981 (etwa 3,3×10²⁴) auf, eine Grenze, die durch rechnerische Verifizierung ermittelt wurde (siehe Sorenson & Webster, 2015, und die weithin reproduzierte deterministische Zeugentabelle, zu der sie gehört). Oberhalb dieser Grenze wird derselbe Test immer noch ausgeführt, aber das Tool sagt Ihnen ehrlich, dass die Garantie zu einer extrem starken probabilistischen und nicht zu einer mathematischen Gewissheit wird.

Die Miller-Rabin-Spur schreibt n − 1 = 2ˢ × d mit d ungerade, durchläuft dann eine echte modulare BigInt-Potenzierung – quadrieren und multiplizieren, wobei Modulo n bei jedem einzelnen Schritt reduziert wird, damit die Zahlen nie explodieren – Stück für Stück für den ersten Zeugen und meldet das Urteil jedes Zeugen, einschließlich des Zeugen, der Zusammengesetztheit nachweist, wenn sich herausstellt, dass die Zahl keine Primzahl ist. Alles läuft lokal in Ihrem Browser: kein Server, keine externe API, keine Daten verlassen jemals Ihr Gerät.