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 2^r, die (n - 1) teilt. Ein Beispiel:

• n = 337, n - 1 = 336
• 2⁸ = 256 teilt 336 nicht.
• 2⁷ = 128 teilt 336 nicht.
• 2⁶ = 64 teilt 336 nicht.
• 2⁵ = 32 teilt 336 nicht.
• 2⁴ = 16 teilt 336 => s = 4

Danach wird d berechnet als (n-1)/2^s. Nun wird ein zufälliges a gewählt, das zwischen 2 und n - 1 liegt. In der ersten Teststufe wird überprüft, ob a^d kongruent 1 modulo n ist. Ist der Test bestanden, dann ist a kein Zeuge und die nächste Zufallszahl muss berechnet werden. Ist a^d 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 a^2r*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.