Test pierwszości Millera-Rabina to probabilistyczny test umożliwiający sprawdzenie czy dana liczba jest złożona czy prawdopodobnie pierwsza. Metoda, w oparciu o którą powstała to deterministyczny algorytm Millera, którego poprawność zależy od nieudowodnionej uogólnionej hipotezy Riemanna. Michael O. Rabin zmodyfikował ten algorytm do postaci testu probablistycznego i dowiódł jego poprawności w tej postaci. Algorytm używany jest do sprawdzania wyłącznie liczb nieparzystych (liczby parzyste - za wyjątkiem dwójki - w sposób oczywisty nie są liczbami pierwszymi). Test Millera-Rabina można zapisać następująco:
k- określa dokładność testu
n - nieparzysta liczba do sprawdzenia

Wylicz s - maksymalną potęgę dwójki dzielącą n-1.
Podstaw d = n/2s
powtórz k razy:
  wylosuj a takie, że 1<a<n
  sprawdź czy ad mod n różne od 1
  jeżeli tak to sprawdz czy ad*2r mod n rozne od n-1 dla wszystkich r, takich że: 0≤r≤s-1
     jeżeli tak to to przerwij test - liczba nie jest pierwsza
jeżeli nie przerwano testu dla żadnej z prób to liczba prawdopodobnie jest pierwsza

Na pierwszy rzut oka trudność sprawiać może obliczenie wartości a^b mod n, szczególnie dla dużych wartości b. Szybko i bezproblemowo obliczymy taką wartość używając algorytmu szybkiego potęgowania modularnego lub dużo wolniejszego, ale prostszego algorytmu naiwnego potęgowania modularnego.

Można pokazać że dla dowolnej złożonej nieparzystej liczby naturalnej n co najmniej 3/4 możliwych wartości a jest dobrymi świadkami złożoności tej liczby. Jeśli zatem przeprowadzamy k losowych prób, prawdopodobieństwo że określimy liczbę złożoną jako pierwszą wynosi co najwyżej 4^-k.


Sprawdzimy z dokładnością k=3, czy liczba n=13 jest pierwsza.
Najpierw obliczymy maksymalną potęge dwójki dzielącą n-1.
12 mod 2 = 0, 12 mod 4 = 0, 12 mod 8 != 0. Zatem maksymalną potęgą dwójki dzielącą 12 jest 4, czyli 4=2^s, s=2.
Obczliymy teraz d = 13/4 = 3 (dzielenie całkowitoliczbowe).
Pierwsza próba a=2.
2³ mod 13 = 8, jest różne od 1, zatem przechodzimy do drugiego sprawdzenia.
r = 0, 2³ mod 13 = 8.
r = 1, 2⁶ mod 13 = 12.
Dla r = 1, a^d*2r mod n równe jest n-1, zatem kontuujemy test.
Druga próba a=6.
6³ mod 13 = 8, jest różne od 1, zatem przechodzimy do drugiego sprawdzenia.
r = 0, 6³ mod 13 = 8.
r = 1, 6⁶ mod 13 = 12.
Dla r = 1, a^d*2r mod n równe jest n-1, zatem kontuujemy test.
Trzecia próba a=11.
11³ mod 13 = 5, jest różne od 1, zatem przechodzimy do drugiego sprawdzenia.
r = 0, 11³ mod 13 = 5.
r = 1, 11⁶mod 13 = 12.
Dla r = 1, a^d*2r mod n równe jest n-1, zatem kontuujemy test.
Wykonaliśmy wszystkie próby, nie stwiedziliśmy, że liczba jest złożona, zatem 13 jest prawdopodobnie liczbą pierwszą.

Sprawdzimy z dokładnością k=3, czy liczba n=9 jest pierwsza.
Najpierw obliczymy maksymalną potęge dwójki dzielącą n-1.
8 mod 2 = 0, 8 mod 4 = 0, 8 mod 8 = 0, 8 mod 16 != 0. Zatem maksymalną potęgą dwójki dzielącą 8 jest 8, czyli 8=2^s, s=3.
Obliczymy d = 8/8 = 1.
Pierwsza próba a=2.
2¹ mod 9 = 2, jest różne od 1, zatem przechodzimy do drugiego sprawdzenia.
r = 0, 2¹ mod 9 = 2.
r = 1, 2² mod 9 = 4.
r = 2, 2⁴ mod 9 = 7.
Wyniki drugiego sprawdzenia są różne od n-1 dla wszystkich r, zatem liczba 9 nie jest liczbą pierwszą, możemy przerwać test.