Test de primalidad de Fermat para niños
El test de primalidad de Fermat es una forma de comprobar si un número grande es probablemente un número primo. Un número primo es un número entero mayor que 1 que solo se puede dividir exactamente por 1 y por sí mismo (como 2, 3, 5, 7). Este test utiliza una regla especial de las matemáticas llamada el Pequeño Teorema de Fermat. Es un test "probabilístico", lo que significa que no siempre nos da una respuesta 100% segura de que un número es primo, pero sí puede decirnos con certeza si un número no es primo.
Contenido
¿Qué es el Pequeño Teorema de Fermat?
El Pequeño Teorema de Fermat es la base de este test. Dice lo siguiente: Si tienes un número p que es primo, y eliges otro número a que no comparte divisores con p (aparte del 1), entonces si elevas a a la potencia de p-1, y luego le restas 1, el resultado siempre será divisible por p.
Esto se puede escribir de una forma más matemática usando la aritmética modular: ap-1 ≡ 1 (mod p)
Esto significa que ap-1 y 1 dejan el mismo resto cuando se dividen por p.
Lo interesante es que, si un número p no es primo (es decir, es un número compuesto), es muy probable que la regla anterior no se cumpla para un número a elegido al azar. Sin embargo, hay algunos números compuestos que pueden "engañar" al test para ciertos valores de a. A estos números se les llama pseudoprimos.
¿Cómo funciona el Test de Primalidad de Fermat?
El test de Fermat es un algoritmo que sigue estos pasos:
- Paso 1: Elige un número grande n que quieres comprobar si es primo.
- Paso 2: Elige un número k que te dice cuántas veces vas a repetir el test. Cuantas más veces lo repitas, más fiable será el resultado.
- Paso 3: Repite los siguientes pasos k veces:
* Elige un número a al azar que sea mayor que 1 y menor que n. * Calcula an-1 (mod n). Esto significa que elevas a a la potencia de n-1, y luego encuentras el resto de esa división entre n. * Si el resultado no es 1, entonces puedes estar seguro de que n no es un número primo. En este caso, el test dice que n es "COMPUESTO".
- Paso 4: Si después de repetir el test k veces, todos los resultados fueron 1, entonces el test dice que n es un "POSIBLE PRIMO". Esto significa que es muy probable que sea primo, pero no hay una certeza del 100% (podría ser un pseudoprimo).
Este proceso se hace muy rápido usando técnicas especiales para calcular potencias grandes, lo que se conoce como exponenciación modular.
Un ejemplo práctico
Imagina que queremos saber si el número 221 es primo.
1. Elegimos un número a al azar entre 1 y 221, por ejemplo, a = 38. 2. Calculamos 38220 (mod 221). 3. Si hacemos los cálculos, obtenemos que 38220 ≡ 1 (mod 221). * ¡Parece que 221 podría ser primo! Pero como es un test probabilístico, no podemos estar seguros. El 38 podría ser un número que "engaña" al test.
4. Así que, elegimos otro número a, por ejemplo, a = 24. 5. Calculamos 24220 (mod 221). 6. Esta vez, el resultado es 24220 ≡ 81 (mod 221). * Como 81 no es igual a 1, ¡sabemos con seguridad que 221 no es un número primo! El número 24 es una "prueba" de que 221 es compuesto. (De hecho, 221 = 13 × 17).
¿Para qué se usa?
El test de primalidad de Fermat es útil en criptografía, que es la ciencia de proteger la información. Por ejemplo, algunos programas de cifrado como PGP (Pretty Good Privacy) lo usan.
Cuando PGP necesita generar números primos muy grandes para crear claves de seguridad, usa este test. Comprueba los números que elige usando los primeros números primos (2, 3, 5 y 7) como valores de a. Si el número pasa el test con estos cuatro valores, se considera que es "probablemente primo" y se usa. Si falla con alguno de ellos, se sabe que no es primo y se descarta. Usar más valores de a hace que el test sea más seguro, pero estos cuatro ya son muy efectivos para la mayoría de los casos.
Véase también
En inglés: Fermat primality test Facts for Kids
