## [Test de Primalidad](/es/node/62907) Definición El proceso algorítmico de decidir si un entero dado es primo, produciendo bien un certificado determinista de primalidad o un veredicto probabilístico que afirma que el número es primo con alta confianza. ## Principio Principio Las pruebas de primalidad explotan propiedades aritméticas que distinguen primos de compuestos (el pequeño teorema de Fermat, condiciones de primo probable fuerte, identidades polinomiales, propiedades de curvas elípticas) y producen ya sea una prueba inequívoca o un testigo aleatorio que indica que un número es casi con seguridad primo. ## Demostración Demostración Ejemplos: pruebas deterministas en tiempo polinómico como AKS (comprueba una congruencia polinómica), algoritmos probabilísticos como Miller–Rabin (prueba de bases de primo probable fuerte) y métodos que generan certificados como ECPP que devuelven una prueba verificable; Miller–Rabin filtra rápidamente compuestos, mientras ECPP puede producir un certificado explícito para primos grandes usados en criptografía. ## Aplicación incorrecta Aplicación incorrecta Confiar en una única prueba de Fermat para afirmar primalidad sin considerar números de Carmichael o testigos compuestos; usar una prueba probabilística donde se requiere una prueba determinista; o aplicar pruebas diseñadas para impares a entradas pares o triviales sin preprocesamiento. ## Consecuencia Consecuencia Las pruebas de primalidad eficientes permiten la generación y validación práctica de primos grandes para protocolos criptográficos y la teoría computacional de números; cuando se produce un certificado determinista se alcanza certeza absoluta apta para verificación formal y pruebas matemáticas. ## Inversión Inversión La inversión es la factorización entera: conocer la factorización completa decide inmediatamente la primalidad pero suele ser computacionalmente mucho más difícil; por el contrario, la prueba de primalidad suele ser mucho más barata que la factorización completa y a veces proporciona certificados sin factorizar. ## Límite Límite Se ocupa de la decisión de primalidad de enteros presentados en forma explícita; excluye tareas relacionadas pero distintas como la factorización entera, la primalidad de enteros algebraicos sin reducción a Z o heurísticas sin límites de error demostrables salvo que sean explícitamente probabilísticas y cuantificadas. ## Tensión semántica Tensión semántica Existe tensión entre pruebas probabilísticas (rápidas, con probabilidad de error muy baja) y pruebas deterministas (más lentas pero ciertas); también entre la prueba como decisión sí/no y la producción de un certificado verificable — ambos logran el objetivo pero sirven a aplicaciones y garantías diferentes. ## Síntesis Síntesis La prueba de primalidad comprende criterios algorítmicos que van desde cheques probabilísticos rápidos hasta pruebas deterministas más lentas que deciden si un entero es primo; equilibra rapidez y certeza según las necesidades de la aplicación y distingue el problema de decisión del más difícil de la factorización completa.