En matemáticas e informática , un certificado de primordialidad o prueba de primordialidad es una prueba formal y sucinta de que un número es primo. Los certificados de primalidad permiten verificar rápidamente la primordialidad de un número sin tener que ejecutar una prueba de primordialidad costosa o poco confiable . Por lo general, "sucinto" significa que la prueba debe ser, como mucho, polinomialmente mayor que el número de dígitos del número en sí (por ejemplo, si el número tiene b bits, la prueba podría contener aproximadamente b 2 bits).
Los certificados de primalidad conducen directamente a pruebas de que problemas como las pruebas de primalidad y el complemento de la factorización de enteros se encuentran en NP , la clase de problemas verificables en tiempo polinómico dado 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 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. Los test de primalidad probabilísticos estándar, tales como la prueba de Baillie-PSW primalidad , el test de primalidad de Fermat , y el test de primalidad de Miller-Rabin también producen certificados compositeness en el caso de que la entrada está compuesta, pero no producen certificados para las entradas principales.
Certificados Pratt
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 tiene un tamaño polinómico y que es verificable en tiempo polinómico. Se basa en la prueba de primalidad de Lucas , que es esencialmente la inversa del pequeño teorema de Fermat con una condición adicional para hacerlo verdadero:
- Teorema de Lucas : Supongamos que tenemos un número entero a tal que:
- a n - 1 ≡ 1 (mod n ),
- para cada factor primo q de n - 1, no es el caso que a ( n - 1) / q ≡ 1 (mod n ).
- Entonces n es primo.
Dado tal a (llamado testigo ) y la factorización prima de n - 1, es simple verificar las condiciones anteriores rápidamente: solo necesitamos hacer un número lineal de exponenciaciones modulares, ya que cada entero tiene menos factores primos que bits, y cada uno de estos se puede hacer mediante exponenciación elevando al cuadrado las multiplicaciones O (log n ) (consulte la notación O grande ). Incluso con la multiplicación de números enteros de la escuela primaria, esto es solo O ((log n ) 4 ) tiempo; usando el algoritmo de multiplicación con el tiempo de ejecución asintótico más conocido, el algoritmo de Schönhage-Strassen , podemos reducirlo a O ((log n ) 3 (log log n ) (log log log n )) tiempo, o usando notación O suave Õ ((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 incluya números compuestos. Por ejemplo, suponga que afirmamos que n = 85 es primo, proporcionando a = 4 y n - 1 = 6 × 14 como la "factorización prima". Entonces (usando q = 6 yq = 14):
- 4 es coprime a 85,
- 4 85−1 ≡ 1 (mod 85),
- 4 (85−1) / 6 ≡ 16 (mod 85), 4 (85−1) / 14 ≡ 16 (mod 85).
Concluiríamos falsamente que 85 es primo. No queremos simplemente forzar al verificador a factorizar el número, por lo que una mejor manera de evitar este problema es proporcionar 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. . Continuamos recursivamente de esta manera hasta que llegamos a un número conocido como primo, como 2. Terminamos con un árbol de números primos, cada uno asociado con un testigo a . Por ejemplo, aquí hay un certificado Pratt completo para el número 229:
- 229 ( a = 6, 229 - 1 = 2 2 × 3 × 19),
- 2 (primo conocido),
- 3 ( a = 2, 3 - 1 = 2),
- 2 (primo conocido),
- 19 ( a = 2, 19 - 1 = 2 × 3 2 ),
- 2 (primo conocido),
- 3 ( a = 2, 3 - 1 = 2),
- 2 (primo conocido).
Se puede demostrar que este árbol de pruebas contiene como máximo valores distintos de 2 mediante una demostración inductiva simple (basada en el teorema 2 de Pratt). El resultado es válido para 3; en general, tome p > 3 y deje que sus hijos en el árbol sean p 1 , ..., p k . Según la hipótesis inductiva, el árbol enraizado en p i contiene como máximo valores, por lo que todo el árbol contiene como máximo
ya que k ≥ 2 y p 1 ... p k = p - 1. 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.
Dado que hay valores O (log n ) distintos de 2, y cada uno requiere como máximo una exponenciación para verificar (y las exponenciaciones dominan el tiempo de ejecución), el tiempo total es O ((log n ) 3 (log log n ) (log log log n )), o Õ ((log n ) 3 ), lo cual es bastante factible para números en el rango con el que suelen trabajar los teóricos computacionales de números.
Sin embargo, aunque es útil en teoría y fácil de verificar, la generación de un certificado 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 primos de Fermat , pero actualmente es mucho más difícil que la simple prueba de primarios para números primos grandes de forma general.
Certificados Atkin – Goldwasser – Kilian – Morain
Para abordar el problema de la generación eficiente de certificados para números más grandes, en 1986 Shafi Goldwasser y Joe Kilian describieron un nuevo tipo de certificado basado en la teoría de las curvas elípticas . [2] Esto a su vez fue utilizado por AOL Atkin y François Morain como base para los certificados Atkin-Goldwasser-Kilian-Morain, que son el tipo de certificados generados y verificados por sistemas de 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 Primes pueden ser certificados rápidamente"):
- Teorema : Supongamos que se nos da:
- un número entero positivo n no divisible por 2 o 3;
- M x , M y , A, B en(los números enteros mod n ) que satisface M y 2 = M x 3 + AM x + B y con 4A 3 + 27B 2 primos entre sí a n ;
- un primo .
- Entonces M = (M x , M y ) es un punto no identitario en la curva elíptica y 2 = x 3 + Ax + B. Sea k M M sumado a sí mismo k veces usando la suma de la curva elíptica estándar. Entonces, si q M es el elemento identidad I, entonces n es primo.
Técnicamente, una curva elíptica solo se puede construir sobre un campo, y es solo un campo si n es primo, por lo que parece que estamos asumiendo el resultado que estamos tratando de demostrar. 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 primos pueden certificarse rápidamente") que si simplemente realizamos cálculos como si la curva estuviera bien definida y no intentamos en ningún momento invertir un elemento sin inversa, la el resultado sigue siendo válido; si encontramos un elemento sin inverso, esto establece que n es compuesto.
Para derivar un certificado de este teorema, primero codificamos M x , M y , A, B yq , luego codificamos recursivamente la prueba de primalidad para q < n , continuando hasta que alcanzamos 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 los números primos excepto una pequeña fracción, 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, una aplicación que es importante en aplicaciones de criptografía , como la generación de claves RSA demostrablemente válidas .
Certificados basados en Pocklington
La generación de primos comprobables basada en variantes del teorema de Pocklington (ver prueba de primalidad de Pocklington ) [4] pueden ser técnicas eficientes para generar primos (el costo es generalmente menor que la generación probabilística) con el beneficio adicional de los certificados de primalidad integrados. Si bien estos pueden parecer números primos especiales, tenga en cuenta que cada número entero primo podría generarse con un algoritmo de generación demostrable basado en Pocklington.
Pruebas de primordialidad de Pocklington
Dejar dónde dónde son primos distintos con un entero mayor que cero y un testigo tal que:
- 1.
( 1 )
- 2. para todos .
( 2 )
Entonces P es primo si se cumple una de las siguientes condiciones:
( a )
( b )
Certificado de Primalidad de Pocklington
Un certificado de primalidad de Pocklington consta del primo P, un conjunto de primos divisor , cada uno con su propio certificado de prima de Pocklington o lo suficientemente pequeño como para ser una prima conocida, y un testigo .
Los bits necesarios para este certificado (y el orden del costo computacional) deben oscilar entre aproximadamente para la versión ( b ) apara la versión ( a )
Un pequeño ejemplo
Dejar . Tenga en cuenta que y , .
Impacto de "PRIMES está en P"
"PRIMES está en P" [7] supuso un gran avance en la informática teórica. Este artículo, publicado por Manindra Agrawal , Nitin Saxena y Neeraj Kayal en agosto de 2002, demuestra que el famoso problema de comprobar la primacía de un número puede resolverse de forma determinista en tiempo polinomial. Los autores recibieron el premio Gödel 2006 y el premio Fulkerson 2006 por este trabajo.
Debido a que la prueba de primalidad ahora se puede realizar de forma determinista en tiempo polinomial utilizando la prueba de primalidad AKS , un número primo podría considerarse un certificado de su propia primalidad. Esta prueba se ejecuta en Õ ((log n ) 6 ) tiempo. En la práctica, este método de verificación es más caro que la verificación de los certificados Pratt, pero no requiere ningún cálculo para determinar el certificado en sí.
Referencias
- ^ Vaughan Pratt. "Cada prime tiene un certificado sucinto". Revista SIAM de Computación , vol. 4, págs. 214-220. 1975. Citas , texto completo .
- ^ Goldwasser, S. y Kilian, J. "Casi todas las primas pueden certificarse rápidamente". Proc. 18 ° STOC. pp. 316–329, 1986. Texto completo .
- ^ Atkin, A OL ; Morain, F. (1993). "Demostración de curvas elípticas y primalidad" (PDF) . Matemáticas de la Computación . 61 (203): 29–68. doi : 10.1090 / s0025-5718-1993-1199989-x . JSTOR 2152935 . Señor 1199989 .
- ^ Pocklington, Henry C. (1914-1916). "La determinación de la naturaleza prima o compuesta de grandes números por el teorema de Fermat". Actas de la Sociedad Filosófica de Cambridge . 18 : 29-30.
- ^ Crandall, Richard; Pomerance, Carl. "Números primos: una perspectiva computacional" (2 ed.). "Springer-Verlag, 175 Fifth Ave, Nueva York, Nueva York 10010, Estados Unidos, 2005".
- ^ Brillhart, John ; Lehmer, DH ; Selfridge, JL (abril de 1975). "Nuevos Criterios de Primaria y Factorizaciones de 2 m ± 1" (PDF) . Matemáticas de la Computación . 29 (130): 620–647. doi : 10.1090 / S0025-5718-1975-0384673-1 . JSTOR 2005583 .
- ^ Agrawal, Manindra ; Kayal, Neeraj ; Saxena, Nitin (septiembre de 2004). "PRIMES está en P" (PDF) . Annals of Mathematics . 160 (2): 781–793. doi : 10.4007 / annals.2004.160.781 . JSTOR 3597229 . Señor 2123939 .
enlaces externos
- Mathworld: Certificado de Primalidad
- Mathworld: Certificado Pratt
- Mathworld: Certificado Atkin-Goldwasser-Kilian-Morain
- The Prime Glossary: Certificate of Primality
- Vašek Chvátal . Notas de la conferencia sobre las pruebas de primordialidad de Pratt . Departamento de Ciencias de la Computación. Universidad Rutgers. Versión PDF en Concordia University .
- Wim van Dam. Prueba del teorema de Pratt [ enlace muerto permanente ] . (Notas de la conferencia, PDF)