Test de primalidad de Fermat
# 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^2n$ × 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.

