Test de primalidad de Adleman-Pomerance-Rumely

En teoría de números computacional, la prueba de primalidad de Adleman-Pomerance-Rumely​ es un algoritmo para determinar si un número es primo. A diferencia de otros algoritmos más eficientes para este fin, evita el uso de números aleatorios, por lo que es un test de primalidad determinístico. Lleva el nombre de sus descubridores, Leonard Adleman, Carl Pomerance y Robert Rumely. La prueba involucra aritmética en cuerpos ciclotómicos.

Más tarde fue mejorado por Henri Cohen y Hendrik Lenstra, y es comúnmente denominado como APR-CL. Puede probar la primalidad de un entero n en el tiempo:

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

Implementaciones de software

• UBASIC proporciona una implementación bajo el nombre de APRT-CLE (APR Test CL extended)
• Una aplicación de factorización que usa APR-CL en ciertas condiciones (código fuente incluido)
• Pari/GP usa APR-CL condicionalmente en su implementación de isprime().
• mpz_aprcl es una implementación de código abierto que utiliza C y GMP.
• LLR de Jean Penné usa APR-CL en ciertos tipos de pruebas principales como una opción alternativa.

Bibliografía

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

• Datos: Q4683276