Testy probabilistyczne Obecnie najbardziej efektywne i najczęściej stosowane są testy probabilistyczne. Korzysta się w nich z losowo wygenerowanych liczb z ustalonego przedziału – pewien dobór tych wartości może dać błędny wynik testu, ale przy wybraniu wystarczająco wielu z nich prawdopodobieństwo takiego zdarzenia jest znikome.
Przebieg testu probabilistycznego wygląda następująco: Wybrać losowo liczbę Sprawdzić pewne równanie zawierające oraz zadaną liczbę Jeśli okaże się fałszywe, zwrócić wynik n jest złożona. Wartość jest wtedy świadkiem złożoności i test można zakończyć. Powtarzać całą procedurę, aż uzyska się wystarczającą pewność.
Jeśli w wystarczająco wielu próbach nie uda się stwierdzić złożoności test zwraca odpowiedź: n jest prawdopodobnie pierwsza.
Najbardziej znanymi testami pierwszości są: Test pierwszości Fermata – prosty do przeprowadzenia, ale niepewny: istnieją liczby złożone (liczby Carmichaela), które przez ten test zawsze zostaną uznane za pierwsze. Test pierwszości Solovaya-Strassena – dający przy każdej próbie 1/2 szans na wylosowanie świadka złożoności. Test Millera-Rabina – dający przy każdej próbie 3/4 szans na wylosowanie świadka złożoności. Ten test jest najczęściej stosowany w kryptografii, gdy wymagana jest szybka weryfikacja pierwszości dużych liczb.