Adleman–Pomerance–Rumelyov praštevilski test

V računalniški teoriji števil, je Adleman–Pomerance–Rumelyov praštevilski test algoritem za določanje praštevila. Za razliko od ostalih, bolj učinkovitih algoritmov za ta namen, se izogiba naključnih števil, torej je to deterministični praštevilski test. Poimenovan je po odkriteljih Leonardu Adlemanu, Carlu Pomerancu in Robertu Rumelyu. Test vključuje aritmetiko v ciklotomnih poljih.

Henri Cohen in Hendrik Willem Lenstra sta ga kasneje izboljšala. Imenoval se je APR-CL. Če je število n praštevilo, lahko izračuna v času:

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

Programerske implementacije

• UBASIC ponuja implementacijo pod imenom APRT-CLE (APR Test CL extended)
• Factoring applet včasih uporablja APR-CL (vključena izvorna koda)
• Pari/GP uporablja APR-CL le v implementaciji isprime()
• mpz_aprcl je odprtokodna implementacija, ki uporablja C in GMP
• Jean Penné's LLR uporablja APR-CL občasno kot praštevilski test kot eno možnost

Viri

• Predloga:Navedi revijo
• Predloga:Navedi revijo
• Predloga:Navedi knjigo
• APR and APR-CL