Dużą liczbę można testować na pierwszość bez szukania wszystkich dzielników
Sprawdzanie pierwszości przez dzielenie liczby przez kolejnych kandydatów jest intuicyjne, ale dla wielkich liczb staje się niepraktyczne. Test Millera–Rabina wykorzystuje własności potęgowania modularnego: dla liczby pierwszej określone relacje muszą zachodzić, a znalezienie „świadka” ich złamania dowodzi złożoności. W wersji probabilistycznej liczba złożona może czasem przejść pojedynczą próbę, dlatego wykonuje się wiele testów z różnymi bazami. Co ważne, wynik „złożona” jest rozstrzygający, natomiast wynik po przejściu prób oznacza „prawdopodobnie pierwsza”. Takie testy są na tyle praktyczne, że Miller–Rabin występuje w standardach NIST dotyczących generowania kandydatów na duże liczby pierwsze.
Pierwszość nie wymaga znalezienia dzielnika
Najbardziej oczywisty test pierwszości liczby n polega na szukaniu dzielnika od 2 do √n. Dla małych liczb działa świetnie. Dla liczb mających setki lub tysiące bitów skanowanie kandydatów jest jednak kompletnie nieadekwatne. Kluczowa zmiana polega na tym, by nie pytać „jaki jest dzielnik?”, lecz „czy n zachowuje się tak, jak musi zachowywać się liczba pierwsza?”.
Test Millera–Rabina korzysta z arytmetyki modulo n i rozkładu n-1 na 2^s·d, gdzie d jest nieparzyste. Dla wybranej bazy a bada ciąg potęg modularnych. Jeżeli zachowanie przeczy warunkom koniecznym dla liczby pierwszej, baza staje się świadkiem złożoności. Nie trzeba przy tym otrzymać konkretnego nietrywialnego dzielnika. Można wiedzieć, że liczba jest złożona, nie wiedząc jeszcze, z czego dokładnie się składa.
„Prawdopodobnie pierwsza” to kontrolowana kategoria
Michael Rabin opisał w 1980 roku praktyczny probabilistyczny algorytm testowania pierwszości dużych liczb. Jego charakter jest jednostronny: gdy test wykaże złożoność, wynik jest pewny. Gdy kandydat przejdzie próbę, może być liczbą pierwszą albo szczególną liczbą złożoną, która dla tej bazy udaje pierwszą — tzw. strong pseudoprime.
Dlatego test powtarza się dla kolejnych baz. Dla każdej nieparzystej liczby złożonej co najmniej duża część możliwych baz ujawnia jej złożoność, więc niezależne próby szybko zmniejszają ryzyko przeoczenia. W praktycznych zastosowaniach liczba rund jest dobierana do rozmiaru kandydatów, sposobu ich generowania i wymaganego poziomu bezpieczeństwa.
NIST ostrzega przed zbyt prostym rozumieniem „prawdopodobieństwa błędu”
W FIPS 186-5 NIST nadal opisuje Miller–Rabin jako probabilistyczny test pierwszości wykorzystywany przy generowaniu parametrów RSA. Dodaje przy tym ważne ostrzeżenie: prawdopodobieństwo, że konkretna liczba złożona przejdzie t rund testu, nie jest tym samym co prawdopodobieństwo, że losowo wybrany kandydat, który przeszedł t rund, jest złożony. Drugie pytanie zależy także od tego, jak często w populacji kandydatów występują liczby pierwsze.
To subtelność często gubiona w popularnych opisach. Stwierdzenie typu „po t próbach ryzyko wynosi dokładnie X” może mieszać prawdopodobieństwo warunkowe z ograniczeniem dotyczącym pojedynczej liczby złożonej. Standardy kryptograficzne dobierają liczbę prób bardziej ostrożnie, uwzględniając model generowania kandydatów.
Dlaczego test pierwszości jest praktycznie ważny
W kryptografii często potrzebne są duże liczby pierwsze, ale nie wybiera się ich z gotowej gigantycznej tabeli. Generuje się kandydatów i testuje ich własności. Szybkie potęgowanie modularne pozwala przeprowadzać próby Millera–Rabina bez operacji proporcjonalnych do wartości samego wykładnika, a seria testów szybko odrzuca liczby złożone.
To jeden z ciekawszych przykładów, w których rozwiązanie pozornie „trudniejszego” problemu omija intuicyjny krok. Aby stwierdzić pierwszość z bardzo wysokim poziomem zaufania, nie trzeba faktoryzować liczby. Testowanie pierwszości i rozkład na czynniki to różne problemy obliczeniowe; znajomość odpowiedzi „to nie jest liczba pierwsza” może być znacznie łatwiejsza niż znalezienie jej czynników.
Świadek złożoności daje informację bez pełnego rozkładu
To rozdzielenie pytań ma duże znaczenie koncepcyjne. Jeśli Miller–Rabin znajdzie świadka, otrzymujemy pewność, że kandydat jest złożony, choć test nie musi ujawnić żadnego z jego czynników. „Czy liczba jest pierwsza?” i „jakie są jej czynniki?” to odrębne zadania obliczeniowe. W praktyce pozwala to szybko filtrować ogromne liczby bez wykonywania faktoryzacji, która może być znacznie trudniejsza. Algorytm wykorzystuje więc własność konieczną liczb pierwszych jako test odrzucający, zamiast próbować rekonstruować całą strukturę liczby złożonej.
Potęgowanie modularne pozwala badać ogromne liczby bez tworzenia ogromnych potęg
Wzory używane w Millerze–Rabinie zawierają potęgi, ale implementacja nie konstruuje liczby a^d w pełnej postaci, a dopiero potem nie dzieli jej przez n. Po każdym mnożeniu można wykonać redukcję modulo n, ponieważ do testu interesuje nas wyłącznie reszta. W połączeniu z potęgowaniem przez kwadratowanie utrzymuje to rozmiar operandów związany z rozmiarem n i pozwala obliczać potęgi o ogromnych wykładnikach w rozsądnej liczbie kroków. To ważne połączenie dwóch idei algorytmicznych: sam test pierwszości jest skuteczny dlatego, że jego podstawowa operacja — modularne potęgowanie — również ma wydajny algorytm. Często złożony system obliczeniowy staje się praktyczny dopiero wtedy, gdy szybkie są wszystkie kluczowe warstwy, a nie tylko najwyższy poziom procedury.