Ein probabilistischer Algorithmus, der prüft, ob eine ungerade ganze Zahl n wahrscheinlich prim ist, indem er eine oder mehrere starke wahrscheinliche-Prim-Überprüfungen für zufällige (oder gewählte) Basen mittels modularer Exponentiation und Quadrierungsregeln durchführt.

Prinzip

Schreibe n-1 = 2^s * d mit d ungerade; für eine Basis a berechne a^d mod n und sukzessive Quadrierungen; wenn keiner dieser Werte 1 oder n-1 im geforderten Muster ist, ist n zusammengesetzt. Wiederholungen mit unabhängigen Basen verringern die Fehlerrate exponentiell.

Demonstration

Teste n=561 mit Basis a=2: Berechne 2^{d} mod 561 und seine Quadrierungen; der Test liefert einen Zeugen für Zusammengesetztheit (561 ist eine Carmichael-Zahl), sodass Miller–Rabin sie für einige Basen als zusammengesetzt erkennt, für andere jedoch ein starker wahrscheinlicher Prim ist — daher werden mehrere Basen eingesetzt.

Fehlanwendung

Ein Miller–Rabin-Ergebnis 'wahrscheinlich prim' als absoluter Beweis für Primalität ansehen ohne genügend Basen, oder zu wenige Runden in kryptographischen Kontexten verwenden, wo der verbleibende Fehler ausgenutzt werden kann.

Konsequenz

Bietet einen schnellen, einfach anpassbaren probabilistischen Primzahltest: Mit einer geeigneten Wahl/Anzahl an Basen wird die Wahrscheinlichkeit, dass eine zusammengesetzte Zahl alle Tests besteht, verschwindend klein; in bestimmten Größenbereichen liefern feste Basen deterministische Resultate.

Umkehrung

Deterministische Primzahlbeweise (z. B. zertifikatbildende Algorithmen) oder vollständige Faktorisierung verwenden, um Gewissheit statt probabilistischer Zusicherung zu erlangen.

Abgrenzung

Nur ein probabilistischer Test: Er liefert 'wahrscheinlich prim' oder 'zusammengesetzt' mit einseitigem Fehler (Zusammengesetzte können bestehen); deterministische Garantien erfordern zusätzliche Runden, ausgewählte Basen für beschränkte Bereiche oder andere Algorithmen.

Semantische Spannung

Im Wettbewerb mit deterministischen und zertifikatsbasierten Primzahltests: Miller–Rabin ist für große Zahlen deutlich schneller und für die Praxis ausreichend, doch seine probabilistische Natur steht im Gegensatz zu beweisenden Primzahlalgorithmen.

Synthese

Miller–Rabin ist ein schneller zufallsbasierter Filter auf der Grundlage modularer Exponentiation und Quadrierung, der durch Wiederholung mit unabhängigen Basen die Wahrscheinlichkeit verringert, eine zusammengesetzte Zahl fälschlich als prim zu klassifizieren, bei gleichzeitig geringem Rechenaufwand.