robot de la enciclopedia para niños

Test de primalidad de Fermat para niños

Enciclopedia para niños

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 ap-1 - 1 es divisible por p. Esto también se puede expresar así:

ap-1 ≡ 1 (mod p).

Resulta que el recíproco de este teorema suele ser verdad: si p es compuesto, entonces ap-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.

  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 × log2n × 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 ≡ 2n-1 ≡ 3n-1 ≡ 5n-1 ≡ 7n-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

Kids robot.svg En inglés: Fermat primality test Facts for Kids

Obtenido de «https://ninos.kiddle.co/index.php?title=Test_de_primalidad_de_Fermat&oldid=4072941»
kids search engine
Todo el contenido de los artículos de la Enciclopedia Kiddle (incluidas las imágenes) se puede utilizar libremente para fines personales y educativos bajo la licencia Atribución-CompartirIgual a menos que se indique lo contrario. Citar este artículo:
Test de primalidad de Fermat para Niños. Enciclopedia Kiddle.