title: Test de primalidad de Fermat
text: # 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.
  
  # Test de primalidad de Fermat
  ## 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$^2$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.
  
  # Test de primalidad de Fermat
  ## 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.
  
  # Test de primalidad de Fermat
  ## 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.