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

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

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

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

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

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

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

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

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.