Prueba de primalidad de Adleman-Pomerance-Rumely

En teoría de números computacionales , 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 . Recibe su nombre en honor a sus descubridores, Leonard Adleman , Carl Pomerance y Robert Rumely . La prueba implica aritmética en campos ciclotómicos .

Posteriormente, Henri Cohen y Hendrik Willem Lenstra lo mejoraron y se lo conoce comúnmente como APR-CL . Puede probar la primalidad de un entero n en el tiempo:

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

Implementaciones de software

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

Referencias

• Adleman, Leonard M. ; Pomerance, Carl ; Rumely, Robert S. (1983). "Sobre la distinción entre números primos y números compuestos". Anales de Matemáticas . 117 (1): 173–206. doi :10.2307/2006975. JSTOR  2006975.
• Cohen, Henri ; Lenstra, Hendrik W. Jr. (1984). "Pruebas de primalidad y sumas de Jacobi". Matemáticas de la computación . 42 (165): 297–330. doi : 10.2307/2007581 . hdl : 1887/2136 . JSTOR  2007581.
• Riesel, Hans (1994). Números primos y métodos informáticos de factorización . Birkhäuser. págs. 131-136. ISBN 978-0-8176-3743-9.
• APR y APR-CL