W 2002 r. opracowanie algorytmu AKS pokazało, że PRIMES leży w klasie P. Nie wiadomo jednak czy PRIMES jest P zupełne, czy należy do zawartych w P klas L (problemy wymagające logarytmicznego rozmiaru pamięci) lub NC (złożoność czasowa na komputerze z wielomianową liczbą procesorów równolegle wykonujących obliczenia).
Linki zewnętrzne Grzegorz Adamski, Ciąg Fibonacciego jako test pierwszości, Poznański Portal Matematyczny, matematyka.poznan.pl, 22 grudnia 2017 [dostęp 2024-10-05]. Testy „pierwszości”, Khan Academy, kanał „KhanAcademyPoPolsku” na YouTube [dostęp 2025-10-27]. [dostęp 2024-03-07].