Test de primalidad de Fermat

El test de primalidad de Fermat es un algoritmo probabilístico que hace uso del pequeño teorema de Fermat. Este teorema 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. Sin embargo, tomando números compuestos n y eligiendo un a coprimo con estos, algunos de ellos pueden hacer fallar este test. Estos números se denominan pseudoprimos.

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.

Ejemplo

Supongamos que se quiere determinar si n = 221 es primo. Escogiendo aleatoriamente 1 < a < 221, digamos a = 38, se puede chequear la expresión para determinar si se cumple:

$a^{n-1}=38^{220}\equiv 1{\pmod {221}}.$

luego 221 puede ser primo, o también puede que 38 sea un número que falsee el test, de manera que tomamos otro a, esta vez 24:

$a^{n-1}=24^{220}\equiv 81\not \equiv 1{\pmod {221}}.$

Luego 221 es compuesto y 38 era en efecto un número que falsaba el test. Además, 24 es un testigo de Fermat de la no primalidad de 221.

Usos

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 n 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^n-1 ≡ 3^n-1 ≡ 5^n-1 ≡ 7^n-1 (mod n), entonces sabe que el número n es probablemente primo. Si de alguna de las expresiones anteriores se obtiene un valor distinto de 1, entonces n es definitivamente compuesto. Utilizar un número mayor de testigos disminuye la probabilidad de que un número compuesto n parezca primo, aunque muy pocos números grandes pueden engañar a los cuatro testigos ya mencionados.

Véase también

• Test de primalidad

Referencias

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). «Section 31.8: Primality testing». Introduction to Algorithms (Second edición). MIT Press; McGraw-Hill. p. 889–890. ISBN 0-262-03293-7. 

Enlaces externos

• Weisstein, Eric W. «Fermat's Primality Test». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

• Datos: Q737492