Test de primalidad de Fermat

El pequeño teorema de Fermat enuncia que si p es primo y a es coprimo con p, entonces

a^p-1 - 1 es divisible por p. Esto también se puede expresar así: a^p-1 = 1 (mod p).

Resulta que el recíproco de este teorema suele ser verdad: si p es compuesto, entonces a^p-1 es poco probable que sea congruente con 1 módulo p para un valor arbitrario de a.

El programa de cifrado PGP aprovecha esta propiedad del teorema para comprobar si los grandes números aleatorios que elige son primos. Comprueba los valores que llamaremos x utilizando 4 valores de a (llamados testigos) utilizando la fórmula anterior. Estos cuatro valores son 2, 3, 5 y 7, los cuatro primeros números primos. Si 1 = 2^x-1 = 3^x-1 = 5^x-1 = 7^x-1 (mod x), entonces sabe que el número x es probablemente primo. Si de alguna de las expresiones anteriores se obtiene un valor distinto de 1, entonces x es definitivamente compuesto. Utilizar un número mayor de testigos disminuye la probabilidad de que un número compuesto x parezca primo, aunque muy pocos números grandes pueden engañar a los cuatro testigos ya mencionados.

El artículo Pseudoprimo ofrece una discusión en profundidad sobre los números que engañan a los tests de primalidad como éstos.

Algoritmo

El algoritmo para implementar el test es el siguiente:

Algoritmo test de primalidad de Fermat (Orden de complejidad $\mathcal O(k \times (\log n)^{2+\epsilon})$)

Entrada: Un número natural n>1, el número k de veces que se ejecuta el test y nos determina la fiabilidad del test. Salida: COMPUESTO si n es compuesto y POSIBLE PRIMO si n es un posible primo. Para $j\,\!$ desde $1\,\!$ hasta $k\,\!$ haga lo siguiente: $a \gets$ Función Genera_numero_aleatorio_en_intervalo$(1,n-1]\,\!$ Si $a^{n-1} \not \equiv 1 \pmod n$ entonces: Retorne COMPUESTO Retorne POSIBLE PRIMO

Utilizando algoritmos rápidos de exponenciación modular, se puede comprobar que el tiempo de ejecución de este algoritmo es O(k × log²n × log log n × log log log n), donde k representa el número de veces que se comprueba la congruencia para el número aleatorio a y n es el número a testear.