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:

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.


Zu testende Zahl n:
Anzahl Tests: