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

• Adleman, Leonard M.; Pomerance, Carl; Rumely, Robert S. (1983). »On distinguishing prime numbers from composite numbers«. Annals of Mathematics. Zv. 117, št. 1. str. 173–206. doi:10.2307/2006975. JSTOR 2006975.
• Cohen, Henri; Lenstra, Hendrik W., Jr. (1984). »Primality testing and Jacobi sums«. Mathematics of Computation. Zv. 42, št. 165. str. 297–330. doi:10.2307/2007581. JSTOR 2007581.
• Riesel, Hans (1994). Prime Numbers and Computer Methods for Factorization. Birkhäuser. str. 131–136. ISBN 978-0-8176-3743-9.
• APR and APR-CL