Test de primalidad
Tests verdaderos de primalidad 
En los apartados anteriores se ha hablado de dos problemas relacionados (factorización y primalidad) que de alguna manera son complementarios. Sin embargo, las dos cuestiones son de naturaleza muy distinta. Para convencer a alguien de que un número ha sido factorizado es suficiente con mostrar los factores y el resultado queda claro. Sin embargo convencer a esa misma persona de que un número dado es primo puede ser mucho más difícil. Como el matemático parisino del siglo XIX Fortuné Landry señaló, a menos que la otra parte conozca los métodos de comprobación de la primalidad y realice por sí misma los cálculos, la sencilla respuesta “es primo” es sólo cuestión de fe. Un test (o chequeo) de primalidad es un algoritmo que, dado un número de entrada n, no consigue verificar la hipótesis de un teorema cuya conclusión es que n es compuesto.
¿Qué hay que mostrar para demostrar que un número ha sido factorizado?
los factores