Już sprawdzenie dwudziestu losowych świadków gwarantuje, że prawdopodobieństwo błędnego rozpoznania liczby jako pierwszej jest mniejsze niż jeden do biliona.
Szybkie testy deterministyczne Istnieje deterministyczny test pierwszości oparty na krzywych eliptycznych, działający w czasie . Jego działanie opiera się jednak na pewnych dotychczas nieudowodnionych twierdzeniach z teorii liczb. Jest skomplikowany w implementacji, ale prawdopodobnie jest to najczęściej używany deterministyczny test pierwszości.
Jeśli uogólniona hipoteza Riemanna jest prawdziwa, test Millera-Rabina można przekształcić w test deterministyczny, działający w czasie . W praktyce jest on jednak wolniejszy od poprzedniego.
W 2002 roku Manindra Agrawal, Nitin Saxena i Neeraj Kayal opublikowali pierwszy deterministyczny wielomianowy test, nie opierający się na żadnych niedowiedzionych założeniach, zwany testem pierwszości AKS. Test ten w oryginalnej wersji działa w czasie choć w praktyce jest wolniejszy od metod probabilistycznych.
Złożoność W teorii złożoności formalnie opisuje się język liczb pierwszych jako PRIMES.