Test pierwszości APR

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Test pierwszości APRalgorytm 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:

\Omicron((\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.