Der Miller-Rabin-Test ist ein Monte-Carlo-Algorithmus zum Testen, ob Zahlen prim sind oder
nicht. Zunächst werden aus der Eingabezahl, die überprüft werden soll, die Zahlen "s" und "d"
berechnet. Hierbei ist "s" der Logarithmus zur Basis 2 der größten Zahl der Form 2r,
die (n-1) teilt. Ein Beispiel:
n = 337, n-1 = 336
28 = 256 teilt 336 nicht.
27 = 128 teilt 336 nicht.
26 = 64 teilt 336 nicht.
25 = 32 teilt 336 nicht.
24 = 16 teilt 336 => s = 4
Danach wird d berechnet als (n-1)/2s. Nun wird ein zufälliges a gewählt, das zwischen 2 und n-1 liegt.
In der ersten Teststufe wird überprüft, ob ad kongruent 1 modulo n ist. Ist der Test bestanden, dann
ist a kein Zeuge und die nächste Zufallszahl muss berechnet werden. Ist ad nicht kongruent 1 modulo n,
dann wird in die zweite Teststufe gegangen: hier wird für alle r, die von 0 bis s-1 laufen, berechnet ob
a2r*d kongruent -1 modulo n ist. Fällt die Zahl hier durch alle Werte von r, so ist klar:
n ist keine Primzahl. a ist Primzahlzeuge für die nicht-primheit von n. Falls auch in der zweiten Stufe
nur ein Test bestanden wird, muss die nächste Zufallszahl berechnet werden. Für jeden bestandenen Test ist
die Wahrscheinlichkeit 1/4, dass dies Zufall war. Die Wahrscheinlichkeit beträgt also bereits nach 5 bestandenen
Tests 99,9%, dass n eine Primzahl ist.