Test pierwszości APR

Test pierwszości APR - algorytm stworzony na początku lat 80. XX wieku przez Leonarda Adlemana, Carla Pomerance'a i Roberta Rumely'ego, służący do dowodzenia, że dana liczba naturalna jest liczbą pierwszą. Jest pierwszym w historii wydajnym w praktyce algorytmem, który był w stanie sprawdzać pierwszość liczb o kilku tysiącach cyfr dziesiętnych. Złożoność czasowa algorytmu (tzw. wariantu Cohena-Lenstry) wynosi:

$O((\log\,n)^{\log\,\log\,\log\,n})$

gdzie n jest liczbą do sprawdzenia. Jest więc niemalże wielomianowo zależna od długości liczby.