"Sucinta" generalmente significa que la prueba debe ser como máximo polinómica, con una cantidad de dígitos no desmesuradamente mayor que número en sí (por ejemplo, si el número tiene b bits, la prueba puede contener aproximadamente b2 bits).
Estos problemas ya se encuentran trivialmente en la categoría co-NP.
El concepto de certificados de primalidad fue introducido históricamente por el certificado 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 el test de Lucas, que es esencialmente la conversión 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 se necesita 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 puede hacerse mediante exponenciación binaria en O(log n) multiplicaciones (véase cota superior asintótica).
Sin embargo, es posible engañar a un criterio verificador para que acepte un número compuesto dándole una "factorización prima" de n−1 que incluya números compuestos.
Entonces (usando q=6 y q=14): Se concluiría falsamente que 85 es primo.
No se desea simplemente obligar al verificador a factorizar el número, por lo que una mejor manera de evitar este problema es otorgar certificados de primalidad para cada uno de los factores primos de n−1 también, que son solo instancias más pequeñas del problema original.
Entonces, se continúa recursivamente de esta manera hasta llegar a un número primo, como 2.
Finalmente, se obtiene un árbol de números primos, cada uno asociado con un testigo a.
Por ejemplo, a continuación se incluye un certificado completo de Pratt para el número 229: Se puede demostrar que este árbol de prueba contiene como máximo
El resultado es válido para 3; en general, tómese p > 3 y que sus hijos en el árbol sean p1, ..., pk.
Por la hipótesis inductiva, el árbol con raíz en pi contiene como máximo
Dado que cada valor tiene como máximo (log n) bits, esto también demuestra que el certificado tiene un tamaño de O((log n)2) bits.
Sin embargo, aunque en teoría es útil y fácil de verificar, generar un certificado de Pratt para n requiere factorizar n−1 y otros números potencialmente grandes.
Esto es simple para algunos números especiales como los números de Fermat, pero actualmente es mucho más difícil que una simple prueba de primalidad para números primos grandes de forma general.
O. L. Atkin y François Morain como base para los certificados Atkin-Goldwasser-Kilian-Morain, que son el tipo de certificados generados y verificados por los sistemas prueba de primalidad de curva elíptica.
[3] Así como los certificados de Pratt se basan en el teorema de Lucas, los certificados de Atkin-Goldwasser-Kilian-Morain se basan en el siguiente teorema de Goldwasser y Kilian (lema 2 de "Casi todos los números primos se pueden certificar rápidamente"): Técnicamente, una curva elíptica solo se puede construir sobre un cuerpo, y
La dificultad surge en el algoritmo de suma de curvas elípticas, que toma inversas en el campo que pueden no existir en
Sin embargo, se puede demostrar (lema 1 de "Casi todos los números primos se pueden certificar rápidamente") que si simplemente se realizan cálculos como si la curva estuviera bien definida y en ningún momento se intenta invertir un elemento sin inverso, el resultado sigue siendo válido; si aparece un elemento sin inverso, entonces esto significa que n es compuesto.
Para deducir un certificado de este teorema, primero se codifican Mx, My, A, B y q, luego se codifica recursivamente la prueba de primalidad para q < n, continuando hasta llegar a un primo conocido.
Este certificado tiene tamaño O((log n)2) y se puede verificar en tiempo O((log n)4).
Además, se puede demostrar que el algoritmo que genera estos certificados es el tiempo polinomial esperado para todos menos una pequeña fracción de números primos, y esta fracción disminuye exponencialmente con el tamaño de los números primos.
En consecuencia, es adecuado para generar grandes números primos aleatorios certificados, un uso que es importante en las aplicaciones de criptografía, como la generación de claves RSA comprobablemente válidas.
Si bien estos pueden parecer primos especiales, debe tenerse en cuenta que cada número primo podría generarse con un algoritmo de generación demostrable basado en el teorema de Pocklington.
un entero mayor que cero y un testigo
(2)Entonces P es primo si se cumple una de las siguientes condiciones: a) (véase[5])
Los bits necesarios para este certificado (y el orden del costo computacional) deben variar desde aproximadamente
"PRIMES is in P"[7] fue un gran avance en la informática teórica.
Esta prueba se ejecuta en tiempo Õ((log n)6).
En la práctica, este método de verificación es más costoso que la verificación de los certificados Pratt, pero no requiere ningún cálculo para determinar el certificado en sí mismo.