Auf dieser Seite können Sie für eine Zahl mit dem Miller-Rabin-Test prüfen, ob diese (wahrscheinlich) eine Primzahl ist, und optional weitere Primzahlen bestimmen.
Der Miller-Rabin-Test prüft, ob eine gegebene Zahl n zusammengesetzt ist. Zunächst wird n-1 in eine ungerade Zahl d und eine Zweierpotenz 2s zerlegt. Daraufhin werden für Zahlen a aus dem Bereich 1<a<n-1 die folgenden Tests durchgeführt:
| Test 1: | Ist ad ≡ 1 mod n |
| Test 2: | für alle i mit 0≤i<s: Gibt es ein i mit ad * 2i ≡ (n-1) mod n |
Falls beide Tests (bei Test2 also die Untertests für alle möglichen i) negativ ausfallen, ist die Zahl definitiv zusammengesetzt; diese Zahl heißt dann Zeuge gegen die Primalität von n. Falls eine Antwort positiv ausfällt, ist die untersuchte Zahl mit einer Wahrscheinlichkeit von höchstens 1:4 zusammengesetzt. Durch mehrfache Wiederholung des Tests für verschiedene Zeugen a erhält man als maximale Wahrscheinlichkeit für eine zusammengesetzte Zahl nach m erfolgreichen Tests einen Wert von (1/4)m.
Mit dem Skript können sowohl einzelne Werte als Zeugen benutzt werden, als auch eine bestimmte Anzahl von Zufallszahlen oder alle Zahlen innerhalb eines Bereiches. Beim Test mit Zufallszahlen werden i.A. weniger Zahlen getestet als angegeben, da vor dem Test geprüft wird, ob eine Zufallszahl bereits verwendet wurde; diese wird dann übersprungen.
Beim deterministischen Test werden nur die Zeugen, die in diesem Wikipedia-Artikel angegeben sind, getestet. Für kleinere Zahlen (bis 3.317.044.064.679.887.385.961.981) liefert das Verfahren dann sehr schnell ein zuverlässiges Ergebnis.