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 sprawdzić 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 pierwszości. Jest więc niemalże wielomianowo zależna od długości liczby.