Test Millera-Rabina – test pierwszości, czyli algorytm określający czy dana liczba jest pierwsza. Podobnie jak test Fermata i test Solovaya-Strassena jest testem probabilistycznym, wymagającym stosowania liczb losowych. Oryginalna wersja tego algorytmu (Millera) została zaprojektowana jako algorytm deterministyczny, jednak jej poprawność zależy od nieudowodnionej dotychczas uogólnionej hipotezy Riemanna. Michael O. Rabin zmodyfikował ten algorytm do postaci randomizacyjnej i dowiódł jego poprawności w tej postaci.
Algorytm i czas działania Algorytm można zapisać w następującej postaci:
Wejście: nieparzysta liczba naturalna do przetestowania; parametr określający dokładność testu.
Wyjście: złożona, jeśli jest złożona, prawdopodobnie pierwsza, jeśli nie uda się stwierdzić złożoności; wylicz maksymalną potęgę dwójki dzielącą i przedstaw jako powtórzyć razy: wybrać losowo ze zbioru jeśli i dla wszystkich ze zbioru zwróć wynik złożona. zwróć wynik prawdopodobnie pierwsza.
Używając algorytmu szybkiego potęgowania można tę procedurę przeprowadzić w czasie , gdzie jest liczbą różnych testowanych wartości
Dowód poprawności Poprawność tego algorytmu opiera się na następujących dwóch twierdzeniach:
Twierdzenie 1 Załóżmy, że jest liczbą pierwszą oraz że
Niech dalej gdzie Wówczas albo albo istnieje dla którego