Algorithmus-Prinzip:
Miller-Rabin ist ein probabilistischer Primzahltest basierend auf einer Erweiterung des kleinen Satzes von Fermat.
a^d ≡ 1 (mod n) 或 a^(2^i × d) ≡ -1 (mod n) 对某个 0 ≤ i < r
Anzahl der Testrunden und Genauigkeit:
- Probabilistischer Test:Wählt zufällig eine Basis a; jede Testrunde reduziert die Fehlerrate auf 1/4
- k Runden testen:Theoretische Fehlerrate ≤ (1/4)^k, tatsächliche Fehlerrate ist viel niedriger
- Deterministischer Test:Für n < 3.317.044.064.679.887.385.961.981 liefert die Verwendung des spezifischen Basissatzes {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} 100% genaue Ergebnisse
Spezialfälle:
- Kleine Primzahlen:Zahlen wie 2, 3, 5, 7 werden direkt identifiziert
- Gerade Zahlen:Alle geraden Zahlen außer 2 sind zusammengesetzt
- Carmichael-Zahlen:Zahlen, die den Fermat-Test bestehen, aber tatsächlich zusammengesetzt sind (z. B. 561), können von Miller-Rabin korrekt identifiziert werden