Benutzer:Abrankov/Miller-Rabin Test/Beispiel

Wir möchten überprüfen, ob 89 mit Miller-Rabin Test eine Primzahl ist. Es gilt ${}n-1=88=2^{3}\cdot 11$, also ${}t=3$. Wir testen für zwei zufällige Zahlen ${}a=3$ und ${}a=5$ erhalten wir:

${}3^{11}\equiv 37\mod n$

${}3^{2.11}\equiv 37^{2}\equiv 34\mod n$

${}3^{4.11}\equiv 37^{2}\equiv -1\mod n$

${}5^{11}\equiv 55\mod n$

${}5^{2.11}\equiv 55^{2}\equiv -1\mod n$

Die zwei Testzahlen erfüllen die Testbedingung.