Ir al contenido

Test de primalidad de Adleman-Pomerance-Rumely

De Wikipedia, la enciclopedia libre

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:

Implementaciones de software

[editar]
  • 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

[editar]
  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. 

Bibliografía

[editar]