Test de primalidad de Adleman-Pomerance-Rumely

En teoría de números computacional, la prueba de primalidad de Adleman-Pomerance-Rumely[1] 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.

Referencias

Yu. I. Manin, Alexei A. Panchishkin (2006). Introduction to Modern Number Theory: Fundamental Problems, Ideas and Theories. Springer Science & Business Media. pp. 69 de 514. ISBN 9783540276920. Consultado el 11 de octubre de 2022.

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

Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.

[YIMAAP-1] Yu. I. Manin, Alexei A. Panchishkin (2006). Introduction to Modern Number Theory: Fundamental Problems, Ideas and Theories. Springer Science & Business Media. pp. 69 de 514. ISBN 9783540276920. Consultado el 11 de octubre de 2022.