En matemáticas y ciencias de la computación, un certificado de primalidad o prueba de primalidad es una prueba sucinta y formal de que un número es primo. Los certificados de primalidad permiten comprobar rápidamente la primalidad de un número sin tener que realizar una prueba de primalidad costosa o poco fiable.

«Sucinta» suele significar que la prueba debe ser como máximo polinómicamente mayor que el número de dígitos del propio número (por ejemplo, si el número tiene b bits, la prueba podría contener aproximadamente b2 bits).

Los certificados de primalidad conducen directamente a la demostración de que problemas como la prueba de primalidad y el complemento de la factorización de enteros se encuentran en NP, la clase de problemas verificables en tiempo polinómico dada una solución.

Estos problemas ya se encuentran trivialmente en co-NP. Esta fue la primera prueba contundente de que estos problemas no son NP-completos, ya que si lo fueran, implicaría que NP es subconjunto de co-NP, un resultado que se creía ampliamente que era falso; de hecho, esta fue la primera demostración de que un problema en NP intersecta co-NP que no se sabía (en ese momento) que estaba en P.

Producir certificados para el problema del complemento, para establecer que un número es compuesto, es sencillo: basta con dar un divisor no trivial.

Más información: es.wikipedia.org