Test de primalidad de Fermat

El algoritmo para implementar el test es el siguiente:

Algoritmo test de primalidad de Fermat (Orden de complejidad ${\displaystyle {\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 ${\displaystyle j\,\!}$ desde ${\displaystyle 1\,\!}$ hasta ${\displaystyle k\,\!}$ haga lo siguiente: ${\displaystyle a\gets }$ Función Genera_numero_aleatorio_en_intervalo${\displaystyle (1,n-1]\,\!}$ Si ${\displaystyle 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.

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:

${\displaystyle 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:

${\displaystyle 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.

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.

• Test de primalidad

• 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.

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