El test de primalidad AKS
------------------------
En agosto de 2002, tres investigadores indios, Manindra Agrawal, Neeraj Kayal y Nitin Saxena, publicaron un artículo en el que proponían un test determinista de primalidad cuyo tiempo de ejecución es comparable al de Rabin–Miller (véase más abajo). Como en este último, la idea básica es una mejora del pequeño teorema de Fermat. Más concretamente, al estudiar los coeficientes binomiales, se demuestra que si a es coprimo con p, entonces p es primo si y solo si los dos polinomios (X – a)*p y Xp – a, con coeficientes en ? / p?, son iguales, es decir, si (X – a)p = Xp – a (mod p*).
Un test basado en esta identidad exige calcular todos los coeficientes del polinomio (X – a)*p, lo que requiere un tiempo prohibitivo. La idea para hacer efectivo este test consiste en evaluar esta identidad módulo el polinomio Xr – 1, es decir, comprobar si (X – a)p = Xp – a (mod Xr – 1, p*).
Si p es primo, esta identidad es cierta para todo par (a, r); por desgracia, el recíproco es falso. Los tres investigadores indios demostraron que, para valores adecuados de r, bastaba comprobar la identidad anterior para cierto número de valores de a para determinar si p es primo o no.
-
El test de primalidad de Miller
------------------------------
Según el pequeño teorema de Fermat, una idea para comprobar si un número p es primo consiste en verificar si *x p *–1 = 1 (mod p) para un valor de x entre 2, 3… p – 1. La programación de este test es sencilla y su tiempo de ejecución, corto. Por desgracia, no siempre da el resultado correcto: si el resultado del test es «verdadero», no es seguro que p sea primo. Así, el entero 341 supera este test, aunque es el producto de 11 por 31. Una forma de sortear la dificultad consiste en estudiar la probabilidad de obtener la respuesta «verdadero» cuando p no es primo. Esta probabilidad es extremadamente baja: la probabilidad de que la respuesta sea «verdadero» aunque p no sea primo al elegir al azar un número entre los veinticinco mil millones más pequeños es de aproximadamente 2 × 10–5.
Una idea sencilla consiste entonces en realizar el test para varios valores de x. A priori, se reduce la probabilidad de error. Michael Rabin (nacido en 1931) y Gary Miller (nacido en 1948) mejoraron esta idea a partir de la factorización del polinomio X *p *–1 – 1. Da lugar a un test del tipo anterior, que se aplica utilizando un entero x. Si se repite para k valores primos de x, el test indica si un número es primo con un riesgo de error del orden de 1 / 4*k. Este test es a priori* probabilístico, pero para números «pequeños» es fácil deducir de él un test determinista.
