Miller-Rabin Primality Test
Miller-Rabin ist ein probabilistischer Primzahltest: Mit n-1=2^s*d wird geprüft, ob a^d≡1 oder ein a^(2^r*d)≡-1 (mod n) gilt; die Falsch-Positiv-Wahrscheinlichkeit beträgt höchstens 1/4 pro Runde.
Zweck
Primalität effizient und probabilistisch testen, genutzt für die RSA-Großprimzahlgenerierung.
Mechanismus
Für n-1=2^s*d wähle ein zufälliges a∈[2,n-2] und berechne x=a^d mod n. Wenn x=1 oder n-1, ist n wahrscheinlich prim. Andernfalls bis zu s-1 Mal quadrieren; erscheint n-1, ist n wahrscheinlich prim, sonst sicher zusammengesetzt. Nach k Runden beträgt der Fehler höchstens 4^(-k).
Anwendungsfälle
- RSA-Primzahlgenerierung
- Primzahltests
- Kryptografische Implementierungen
Verwandte Tools
Primzahl-Prüfer
Prime Checker — reines Client-seitiges Tool. Datenschutz zuerst, kein Server-Roundtrip. WERKZEUG
Primzahl-Generator
Prime Generator — reines Client-seitiges Tool. Datenschutz zuerst, kein Server-Roundtrip. WERKZEUG
Miller-Rabin-Primzahltest
Miller Rabin Primality Test — reines Client-seitiges Tool. Datenschutz zuerst, kein Server-Roundtrip. WERKZEUG