Deterministischer Miller–Rabin-Test

Der deterministische Miller–Rabin-Test entscheidet, ob eine ganze Zahl n prim ist, indem er den starken wahrscheinlich-primen Zeugentest gegen eine kurze, feste Liste von Basen ausführt, die jede ganze Zahl unterhalb einer veröffentlichten Garantieschranke korrekt entscheiden. Im Gegensatz zu einem probabilistischen Miller–Rabin-Lauf, der zufällige Zeugen zieht und nur den Fehler schätzt, verwendet diese Fähigkeit stets dieselben Basen, liefert für dasselbe n stets dasselbe Urteil und lehnt Eingaben ab, die oberhalb der Schranke liegen, in der diese Basen nicht mehr als ausreichend bewiesen sind. Sie senden eine einzelne ganze Zahl von mindestens zwei bis höchstens zur Schranke und erhalten ein Prim-Flag, die Zeugenliste, die Schranke selbst und—wenn die Zahl zusammengesetzt ist—den ersten Zeugen, der das bewiesen hat.

So arbeitet der starke wahrscheinlich-prime Test mit festen Basen

Miller–Rabin schreibt einen ungeraden Kandidaten n um als n minus eins gleich d mal zwei hoch s mit ungeradem d und berechnet dann für jeden Zeugen a die Potenz a hoch d modulo n. Ist diese Potenz eins oder n minus eins, besteht der Zeuge. Andernfalls quadriert der Algorithmus den Wert bis zu s minus einer Mal und akzeptiert den Zeugen nur, wenn irgendein Zwischenquadrat n minus eins ergibt; jeder andere Pfad beweist, dass n für diese Basis zusammengesetzt ist.

Eine Zahl, die jeden Zeugen besteht, heißt stark wahrscheinlich prim zu diesen Basen. Für sorgfältig gewählte feste Mengen zeigen zahlentheoretische Ergebnisse, dass es unter einer bekannten Schwelle keine zusammengesetzte Zahl gibt, die alle Basen der Menge täuscht—so wird das wahrscheinlich-prime Ergebnis innerhalb der Schranke zu einem echten Primurteil. Diese Fähigkeit verwendet die sieben Basen zwei, drei, fünf, sieben, elf, dreizehn und dreiundzwanzig, die für jede 64-Bit-Ganzzahl und damit für jede sichere JavaScript-Ganzzahl bis neun Billiarden ausreichen.

Die winzigen Primzahlen zwei und drei werden als prim entschieden. Teilt ein Zeuge n und ist kleiner als n, wird dieser Zeuge als fehlgeschlagene Basis gemeldet, weil n ein offensichtliches Vielfaches ist.

Wann ein Primtest mit festen Basen hilft

Kryptographie-Kurse und CTF-Trainer nutzen einen deterministischen Miller–Rabin-Test, um Studierenden den Unterschied zwischen probabilistischen Prüfungen mit Zufallszeugen und Zertifikaten fester Basen zu zeigen, die ihre Garantieschranke in der Antwort nennen. Bibliotheksautoren verankern Unit-Tests gegen bekannte Primzahlen, starke Pseudoprimzahlen und Zusammengesetzte, damit ein Refactor der modularen Exponentiation ein Urteil nicht still umkippt. Anwendungsentwickler validieren primförmige Konfigurationswerte, Puzzle-Saaten oder Spielzeug-Diffie–Hellman-Parameter vor einer längeren Pipeline und fangen gerade Werte und kleine Zusammengesetzte ab, ohne ein Computeralgebrasystem aufzusetzen.

Bevorzugen Sie dieses Werkzeug, wenn die Suchabsicht genau der deterministische Miller–Rabin-Algorithmus mit festen Zeugen und harter Schranke ist—nicht wenn Sie den kleinsten Teiler einer Zusammengesetzten, die vollständige Primfaktorisierung, Lucas–Lehmer für Mersenne-Zahlen oder probabilistische Tests mit einer von Ihnen gelieferten benutzerdefinierten Zeugenliste brauchen.