Prueba de primalidad de Fermat: método probabilístico y limitaciones
Prueba probabilística de primalidad basada en el pequeño teorema de Fermat; es simple y rápida, pero puede fallar con ciertos compuestos, como pseudoprimos y números de Carmichael.
Resumen
La prueba de primalidad de Fermat es un método probabilístico sencillo para comprobar si un entero n probablemente es primo. Se basa en el pequeño teorema de Fermat: si p es primo y a es cualquier entero con 1 < a < p, entonces a^(p-1) ≡ 1 (mod p). La prueba elige una o varias bases a y verifica si se cumple la congruencia; si falla, demuestra que n es compuesto, mientras que si tiene éxito convierte a n en un primo probable.
Cómo funciona la prueba
El procedimiento básico es fácil de describir e implementar. Para una base a elegida (1 < a < n):
- Calcula a^(n-1) mod n mediante exponenciación modular rápida.
- Si el resultado no es 1, n es compuesto.
- Si el resultado es 1, n es un primo probable respecto de la base a (un primo probable de Fermat).
Las pruebas repetidas con distintas bases reducen la posibilidad de que un número compuesto pase por casualidad. Muchas implementaciones usan varias bases aleatorias o seleccionadas para aumentar la confianza. Consulta más notas en más sobre el algoritmo.
Limitaciones y pseudoprimos
La prueba de Fermat es rápida, pero imperfecta. Algunos números compuestos satisfacen a^(n-1) ≡ 1 (mod n) para muchas o todas las a coprimas con n; esos números se llaman números de Carmichael y pueden engañar a la prueba, haciendo que declare un compuesto como primo probable. Un número que pasa la prueba para una base a concreta se llama pseudoprimo de Fermat respecto de esa base. Para orientación, véase números de Carmichael y material relacionado.
Historia y uso práctico
La prueba se remonta a ideas en torno al pequeño teorema de Fermat y se ha usado desde los primeros trabajos de teoría computacional de números como un filtro rápido inicial en la detección de primos. Sigue siendo útil cuando se necesitan comprobaciones muy rápidas y de bajo coste, por ejemplo como paso preliminar antes de aplicar pruebas más fuertes. Sin embargo, debido a los falsos positivos, no se recomienda por sí sola para la generación de claves criptográficas; se prefieren pruebas deterministas o pruebas probabilísticas más fuertes, como la prueba de primo probable fuerte de Miller-Rabin. Hay más recursos y comparaciones en referencias detalladas.
Datos destacados: la prueba es muy rápida en la práctica porque la exponenciación modular puede realizarse en tiempo polinómico. Su sencillez la convierte en una herramienta educativa útil y en un paso intermedio hacia algoritmos de primalidad más robustos.
Artículos relacionados
Autor
AlegsaOnline.com Prueba de primalidad de Fermat: método probabilístico y limitaciones Leandro Alegsa
URL: https://es.alegsaonline.com/art/34031