En matemáticas e informática , un certificado de primalidad o prueba de primalidad es una prueba formal y sucinta 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 . "Sucinto" por lo general significa que la demostración debe ser polinomialmente más grande que el número de dígitos del número en sí (por ejemplo, si el número tiene b bits, la demostración podría contener aproximadamente b 2 bits).
Los certificados de primalidad conducen directamente a pruebas 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 polinomial dada una solución. Estos problemas ya se encuentran trivialmente en co-NP . Esta fue la primera evidencia sólida de que estos problemas no son NP-completos , ya que si lo fueran, implicaría que NP es un subconjunto de co-NP, un resultado que se cree que es falso; de hecho, esta fue la primera demostración de un problema en NP intersect co-NP que, en ese momento, no se sabía 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. Las pruebas de primalidad probabilística estándar, como la prueba de primalidad de Baillie-PSW , la prueba de primalidad de Fermat y la prueba de primalidad de Miller-Rabin, también producen certificados de composición en el caso de que la entrada sea compuesta, pero no producen certificados para entradas principales.
El concepto de certificados de primalidad fue introducido históricamente por el certificado de Pratt , concebido en 1975 por Vaughan Pratt , [1] quien describió su estructura y demostró que tenía tamaño polinomial y que era verificable en tiempo polinomial. Se basa en la prueba de primalidad de Lucas , que es esencialmente lo contrario del pequeño teorema de Fermat con una condición adicional para que sea cierto:
Dado tal a (llamado testigo ) y la descomposición en factores primos de n − 1, es simple verificar rápidamente las condiciones anteriores: solo necesitamos hacer un número lineal de exponenciaciones modulares, ya que cada número entero tiene menos factores primos que bits, y cada uno de estos se puede hacer por exponenciación elevando al cuadrado en multiplicaciones O (log n ) (ver notación O grande ). Incluso con la multiplicación de enteros de la escuela primaria, esto es solo O((log n ) 4 ) tiempo; usando el algoritmo de multiplicación con tiempo de ejecución asintótico mejor conocido, el algoritmo de Schönhage-Strassen , podemos reducir esto a O((log n) 3 (log log n )(log log log n )) tiempo, o usando la notación Soft-O Õ((log n ) 3 ).
Sin embargo, es posible engañar a un verificador para que acepte un número compuesto dándole una "factorización prima" de n − 1 que incluye números compuestos. Por ejemplo, supongamos que afirmamos que n = 85 es primo, proporcionando a = 4 y n − 1 = 6 × 14 como la "factorización prima". Entonces (usando q = 6 y q = 14):