Primos y criptografía · Definición

Test de primalidad de Fermat

teoría de números elementalprimos y criptografía

Antes de empezar necesitas conocer

Este test aprovecha el pequeño teorema de Fermat para detectar compuestos de forma rápida. Su fallo principal es que algunos compuestos pasan la prueba para ciertas bases.

Definición

El test de primalidad de Fermat es un criterio probabilístico para un entero \(n>1\): declara compuesto a \(n\) si, para alguna base \(a\) coprima con \(n\), la potencia \(a^{n-1}\) no es congruente con 1 módulo \(n\).

\[a^{n-1} \equiv 1 \pmod{n}\]

Si n es primo y mcd(a, n) = 1, entonces \( a^{n-1} \equiv 1 \pmod{n} \). Por tanto, si para alguna base a con mcd(a, n) = 1 se cumple \( a^{n-1} \not\equiv 1 \pmod{n} \), entonces n es compuesto. El recíproco no vale en general: que se cumpla la congruencia para una base no garantiza primalidad. Para calcular potencias módulo n se usa exponenciación rápida, de modo que cada prueba cuesta \( O(\log n) \) multiplicaciones modulares.

Ejemplo guía: para n = 15 y a = 2, se tiene \( 2^{14} = 16384 \), y \( 16384 \bmod 15 = 4 \neq 1 \). Como la congruencia falla, 15 es compuesto. Sin calcular la potencia completa, basta reducir: \( 2^4 \equiv 1 \pmod{15} \), luego \( 2^{14} = 2^{12} \cdot 2^2 \equiv 4 \pmod{15} \).

Error típico: concluir que n es primo porque \( a^{n-1} \equiv 1 \pmod{n} \) para una sola base. El número 341 = 11·31 cumple \( 2^{340} \equiv 1 \pmod{341} \) y, sin embargo, es compuesto; por eso se deben probar varias bases.

Para pensar

¿Por qué una sola base no basta para afirmar que n es primo?

Porque algunos compuestos, como 341, cumplen la congruencia para una base; hay que probar varias.

Ejercicios 10

  1. ¿Qué indica que \( a^{n-1} \not\equiv 1 \pmod{n} \) con mcd(a, n) = 1?
  2. ¿Cuál es el valor de \( 2^{4} \bmod 15 \)?
  3. ¿Cómo se llama la prueba que usa \( a^{n-1} \equiv 1 \pmod{n} \) para detectar compuestos?
  4. ¿Qué condición debe cumplir la base a en el test de Fermat?
  5. Si n es primo y mcd(a, n) = 1, ¿qué se cumple?
  6. Calcula \( 3^{6} \bmod 7 \) y di si el test con base 3 concluye que 7 es primo o compuesto.
  7. Usa el test con base 2 para n = 9. ¿Qué concluyes?
  8. Para n = 13 y a = 5, ¿cuál es el residuo de \( 5^{12} \bmod 13 \)?
  9. Para n = 21 y a = 2, ¿qué resultado da el test de Fermat?
  10. Demuestra con el test de base 2 que 341 es compuesto, o explica por qué no puede detectarlo y qué base lo delata.

Referencias

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 5 y 16
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2