Implementación de algoritmos de teoría de números/Algoritmos aplicados al problema de la primalidad
La cuestión de la determinación de si un número n dado es primo es conocida como el problema de la primalidad.
Un test de primalidad (o chequeo de primalidad) es un algoritmo probabilístico que, dado un número de entrada n, no consigue verificar de forma concluyente la hipótesis de un teorema cuya conclusión es que n es compuesto. Esto es, un test de primalidad solo conjetura que “ante la falta de certificación sobre la hipótesis de que n es compuesto podemos tener cierta confianza en que se trata de un número primo”. Esta definición supone un grado menor de confianza que lo que se denomina demostración de primalidad (o test verdadero de primalidad), que ofrece una seguridad matemática al respecto.
Un algoritmo de demostración de primalidad (o test verdadero de primalidad) es un algoritmo determinista que, dado un número de entrada n, verifica la hipótesis de un teorema cuya conclusión es que n es primo. Una demostación de primalidad es la verificación computacional de dicho teorema.
Así pues se puede hablar de dos grados de certidumbre: las demostraciones de primalidad (existe certidumbre matemática) y los tests de primalidad (existe certidumbre práctica).