Implementación de algoritmos de teoría de números/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}\equiv 1{\pmod {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 un número compuesto n y eligiendo un a coprimo con este, algunos números compuestos pueden hacer fallar este test. Estos números se denominan pseudoprimos.

Algoritmo

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.

1. Para $j\,\!$ desde $1\,\!$ hasta $k\,\!$ haga lo siguiente:
   1. $a\gets$ Función Genera_numero_aleatorio_en_intervalo$(1,n-1]\,\!$
   2. Si $a^{n-1}\not \equiv 1{\pmod {n}}$ entonces:
      1. Retorne COMPUESTO
2. 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.