Miller-Rabin-Primzahltest-Rechner

Über diesen Rechner

Der Miller-Rabin-Test prüft die Primalität, indem er n − 1 als 2ˢ·d mit ungeradem d schreibt und dann testet, ob eine Zeugen-Basis a die Bedingung aᵈ ≡ 1 (mod n) oder a^(2ʳ·d) ≡ −1 (mod n) für ein r < s erfüllt. Ein einzelner Zeuge liefert nur ein probabilistisches Ergebnis, aber der Test gegen eine kleine, bewiesene Menge fester Zeugen-Basen (zum Beispiel 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) macht den Test für jede ganze Zahl unterhalb von etwa 3,18 × 10²³ deterministisch – weit mehr, als die meisten Anwendungen je benötigen.

Kryptografen und Softwareentwickler verwenden genau diese Art von Test, wenn sie große Primzahlkandidaten für RSA- oder Diffie-Hellman-Schlüssel erzeugen, und Informatikstudierende nutzen ihn, um an echten Zahlen zu sehen, warum Miller-Rabin so viel besser skaliert als die Probedivision, wenn geprüft werden soll, ob eine große ganze Zahl prim ist.