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:
gdzie jest liczbą do sprawdzenia pierwszości. Jest więc niemalże wielomianowo zależna od długości liczby.
- p
- d
- e
Teoria liczb
ogólne typy liczb |
| ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
relacje |
| ||||||||||
działania | |||||||||||
liczby pierwsze |
| ||||||||||
równania diofantyczne |
| ||||||||||
twierdzenia arytmetyki modularnej |
| ||||||||||
inne zagadnienia | |||||||||||
twierdzenia limitacyjne |