En la teoría computacional de números , 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 propósito, evita el uso de números aleatorios, por lo que es una prueba de primalidad determinista . Lleva el nombre de sus descubridores, Leonard Adleman , Carl Pomerance y Robert Rumely . La prueba involucra aritmética en campos ciclotómicos .
Posteriormente fue mejorado por Henri Cohen y Hendrik Willem Lenstra , comúnmente conocido como APR-CL . Puede probar la primordialidad de un número entero n en el tiempo:
Implementaciones de software
- UBASIC proporciona una implementación con el nombre APRT-CLE (APR Test CL extendido)
- Un subprograma 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é utiliza APR-CL en ciertos tipos de pruebas principales como una opción alternativa.
Referencias
- Adleman, Leonard M .; Pomerance, Carl ; Rumely, Robert S. (1983). "Sobre la distinción de números primos de números compuestos". Annals of Mathematics . 117 (1): 173–206. doi : 10.2307 / 2006975 . JSTOR 2006975 .
- Cohen, Henri ; Lenstra, Hendrik W., Jr. (1984). "Pruebas de primordialidad y sumas de Jacobi" . Matemáticas de la Computación . 42 (165): 297–330. doi : 10.2307 / 2007581 . JSTOR 2007581 .
- Riesel, Hans (1994). Números primos y métodos informáticos de factorización . Birkhäuser. pp. 131 -136. ISBN 978-0-8176-3743-9.
- APR y APR-CL