Certificado de primalidad

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 . "Sucinta" suele significar que la prueba debe ser, como máximo, polinómicamente mayor que el número de dígitos del número en sí (por ejemplo, si el número tiene b bits, la prueba puede contener aproximadamente b ² 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 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 ampliamente 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 estuviera en P.

La obtención de certificados para el problema del complemento, a fin de establecer que un número es compuesto, es sencilla: basta con dar un divisor no trivial. Las pruebas de primalidad probabilísticas 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 primos.

Certificados Pratt

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 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 el inverso del pequeño teorema de Fermat con una condición añadida para que sea verdadero:

Teorema de Lucas : Supongamos que tenemos un entero a tal que:

• a ^{n − 1} ≡ 1 (mód 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 un a (llamado testigo ) y la factorización prima de n  − 1, es sencillo verificar rápidamente las condiciones anteriores: solo necesitamos hacer un número lineal de exponenciaciones modulares, ya que cada entero tiene menos factores primos que bits, y cada una de estas se puede hacer por exponenciación elevando al cuadrado en multiplicaciones de O(log n ) (ver notación O grande ). Incluso con la multiplicación de enteros de primaria, esto es solo O((log n ) ⁴ ) tiempo; usando el algoritmo de multiplicación con el tiempo de ejecución asintótico más conocido, debido a David Harvey y Joris van der Hoeven, podemos reducirlo a O((log n ) ³ (log log n )) tiempo, o usando la notación O suave Õ((log n ) ³ ).

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, 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):

• 4 es coprimo de 85,
• 4 ⁸⁵⁻¹ ≡ 1 (mód 85),
• 4 ^(85−1)/6 ≡ 16 (mod 85), 4 ^(85−1)/14 ≡ 16 (mod 85).

Concluiríamos erróneamente que 85 es primo. No queremos simplemente obligar al verificador a factorizar el número, por lo que una mejor manera de evitar este problema es dar certificados de primalidad también para cada uno de los factores primos de n  − 1, que son simplemente instancias más pequeñas del problema original. Continuamos recursivamente de esta manera hasta que llegamos a un número que sabemos que es 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 ²  × 3 × 19),
  • 2 (primo conocido),
  • 3 ( a  = 2, 3 − 1 = 2),
    • 2 (primo conocido),
  • 19 ( a  = 2, 19 − 1 = 2 × 3 ² ),
    • 2 (primo conocido),
    • 3 ( a  = 2, 3 − 1 = 2),
      • 2 (primo conocido).

Se puede demostrar que este árbol de prueba contiene como máximo valores distintos de 2 mediante una prueba inductiva simple (basada en el teorema 2 de Pratt). El resultado es válido para 3; en general, tomemos p > 3 y dejemos que sus hijos en el árbol sean p ₁ , ..., p _k . Por la hipótesis inductiva, el árbol con raíz en p _i contiene como máximo valores, por lo que el árbol entero contiene como máximo ${\displaystyle 4\log _{2}n-4}$ ${\displaystyle 4\log _{2}p_{i}-4}$

${\displaystyle 1+\sum _{i=1}^{k}(4\log _{2}p_{i}-4)=-4k+4\log _{2}p_{1}\cdots p_{k}\leq 4\log _{2}p-4,}$

dado que k ≥ 2, y p ₁ ... 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 ) ² ) bits.

Dado que hay O(log n ) valores distintos de 2, y cada uno requiere como máximo una exponenciación para verificarse (y las exponenciaciones dominan el tiempo de ejecución), el tiempo total es O((log n ) ³ (log log n )(log log log n )), o Õ((log n ) ³ ), lo cual es bastante factible para números en el rango con el que los teóricos de números computacionales suelen trabajar.

Sin embargo, si bien es útil en teoría y fácil de verificar, generar 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 primos de Fermat , pero actualmente mucho más difícil que la simple prueba de primalidad para primos grandes de forma general.

Certificados Atkin-Goldwasser-Kilian-Morain

Para abordar el problema de la generación eficiente de certificados para números mayores, en 1986 Shafi Goldwasser y Joe Kilian describieron un nuevo tipo de certificado basado en la teoría de curvas elípticas . ^[2] Esto fue a su vez 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 Pratt se basan en el teorema de Lucas, los certificados Atkin–Goldwasser–Kilian–Morain se basan en el siguiente teorema de Goldwasser y Kilian (lema 2 de "Casi todos los números primos pueden certificarse rápidamente"):

Teorema : Supongamos que nos dan:

• un entero positivo n no divisible por 2 o 3;
• M _x , M _y , A, B en (los enteros módulo n ) que satisfacen M _y ² = M _x ³ + AM _x + B y con 4A ³ + 27B ² coprimos con n ; ${\displaystyle \mathbb {Z} _{n}}$
• un primo . ${\displaystyle q>n^{1/2}+1+2n^{1/4}}$

Entonces M = (M _x , M _y ) es un punto no identidad en la curva elíptica y ² = x ³ + Ax + B. Sea k M M sumado a sí mismo k veces usando la suma estándar de curvas elípticas. Entonces, si q M es el elemento identidad I, entonces n es primo.

Técnicamente, una curva elíptica sólo puede construirse sobre un cuerpo, y sólo es un cuerpo 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 adición de curvas elípticas, que toma inversas en el cuerpo 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 en ningún momento intentamos invertir un elemento sin inversa, el resultado sigue siendo válido; si encontramos un elemento sin inversa, esto establece que n es compuesto. ${\displaystyle \mathbb {Z} _{n}}$ ${\displaystyle \mathbb {Z} _{n}}$

Para obtener un certificado a partir de este teorema, primero codificamos M _x , M _y , A, B y q , luego codificamos recursivamente la prueba de primalidad para q < n , continuando hasta que llegamos a un primo conocido. Este certificado tiene un tamaño de O((log n ) ² ) y se puede verificar en un tiempo de O((log n ) ⁴ ). Además, se puede demostrar que el algoritmo que genera estos certificados es un tiempo polinomial esperado para todos los primos, excepto una pequeña fracción, y esta fracción disminuye exponencialmente con el tamaño de los primos. En consecuencia, es muy adecuado para generar primos aleatorios grandes certificados, una aplicación que es importante en aplicaciones de criptografía, como la generación de claves RSA demostrablemente válidas .

Certificados con sede en Pocklington

La generación de primos demostrables basada en variantes del teorema de Pocklington (ver prueba de primalidad de Pocklington ) ^[4] puede ser una técnica eficiente para generar primos (el costo es generalmente menor que la generación probabilística) con el beneficio adicional de contar con certificados de primalidad incorporados. Si bien estos pueden parecer primos especiales, observe que cada entero primo podría generarse con un algoritmo de generación de primos demostrables basado en Pocklington.

Pruebas de primalidad de Pocklington

Sean donde donde son primos distintos con un entero mayor que cero y un testigo tales que: ${\displaystyle P=Rh+1}$ ${\displaystyle R=\prod q_{j}^{e_{j}}}$ ${\displaystyle q_{j}}$ ${\displaystyle e_{j}}$ ${\displaystyle g}$

Entonces P es primo si se cumple una de las siguientes condiciones:

Certificado de primalidad de Pocklington

Un certificado de primalidad de Pocklington consta del primo P, un conjunto de primos que dividen a , cada uno con su propio certificado de primo de Pocklington o lo suficientemente pequeño como para ser un primo conocido, y un testigo . ${\displaystyle q_{j}}$ ${\displaystyle (P-1)}$ ${\displaystyle g}$

Los bits necesarios para este certificado (y el orden del costo computacional) deben oscilar aproximadamente entre para la versión ( b ) y para la versión ( a ). ${\displaystyle \log _{2}{P}\left(1+\sum _{k=1}^{\infty }{\frac {1}{3^{k}}}\right)=1.5\log _{2}{P}}$ ${\displaystyle \log _{2}{P}\left(1+\sum _{k=1}^{\infty }{\frac {1}{2^{k}}}\right)=2\log _{2}{P}}$

Un pequeño ejemplo

Sea . Nótese que y , . ${\displaystyle P=1056893}$ ${\displaystyle (P-1)=1621\cdot 163\cdot 2^{2}}$ ${\displaystyle P^{1/2}=1028.053\ldots }$ ${\displaystyle P^{1/3}=101.86156\ldots }$

• Utilizando el 'testigo' 2, se satisface la ecuación 1 y 2 utilizando y . ${\displaystyle q=163}$ ${\displaystyle q=1621}$
• Para la versión a , el certificado solo necesita . ${\displaystyle P=1056893,\ q=1621,\ g=2}$
• Para la versión b , el certificado solo necesita , pero hay un poco más de trabajo por hacer: ${\displaystyle P=1056893,\ q=163,\ g=2}$
  • ${\displaystyle h=(1056893-1)/163=6484}$
  • ${\displaystyle a\equiv h\equiv 127{\bmod {163}}}$y ${\displaystyle b=\left(6484-127\right)/163=39}$
  • El uso falla: ${\displaystyle r=3}$ ${\displaystyle \left(127^{2}-4\cdot 39\right)^{(3-1)/2}\equiv (1^{2}-0)^{1}\equiv 1{\bmod {3}}}$
  • El uso tiene éxito: , y es primo. ${\displaystyle r=5}$ ${\displaystyle \left(127^{2}-4\cdot 39\right)^{(5-1)/2}\equiv (2^{2}-1)^{2}\equiv 2{\bmod {5}}}$ ${\displaystyle P}$

Impacto de “PRIMES está en P”

"PRIMES is in P" ^[7] fue 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 primalidad de un número se puede resolver de forma determinista en tiempo polinómico. Los autores recibieron el Premio Gödel 2006 y el Premio Fulkerson 2006 por este trabajo.

Dado que ahora es posible realizar pruebas de primalidad de manera determinista en tiempo polinomial mediante la prueba de primalidad AKS , un número primo podría considerarse en sí mismo un certificado de su propia primalidad. Esta prueba se ejecuta en un tiempo de Õ((log n ) ⁶ ). En la práctica, este método de verificación es más costoso que la verificación de certificados Pratt, pero no requiere ningún cálculo para determinar el certificado en sí.

Referencias

1. Vaughan Pratt. "Cada número primo tiene un certificado sucinto". SIAM Journal on Computing , vol. 4, págs. 214-220. 1975. Citas, texto completo.
2. Goldwasser, S. y Kilian, J. "Casi todos los materiales de primera calidad pueden certificarse rápidamente". Proc. 18th STOC. págs. 316–329, 1986. Texto completo.
3. Atkin, A OL ; Morain, F. (1993). "Curvas elípticas y demostración de primalidad" (PDF) . Matemáticas de la computación . 61 (203): 29–68. Bibcode :1993MaCom..61...29A. doi : 10.1090/s0025-5718-1993-1199989-x . JSTOR  2152935. MR  1199989.
4. Pocklington, Henry C. (1914–1916). "La determinación de la naturaleza prima o compuesta de los grandes números mediante el teorema de Fermat". Actas de la Sociedad Filosófica de Cambridge . 18 : 29–30.
5. Crandall, Richard; Pomerance, Carl. "Números primos: una perspectiva computacional" (2.ª ed.). Springer-Verlag, 175 Fifth Ave, Nueva York, Nueva York 10010, EE. UU., 2005.
6. Brillhart, John ; Lehmer, DH ; Selfridge, JL (abril de 1975). "Nuevos criterios de primalidad y factorizaciones de 2m ± 1" (PDF) . Matemáticas de la computación . 29 (130): 620–647. doi : 10.1090/S0025-5718-1975-0384673-1 . JSTOR  2005583.
7. Agrawal, Manindra ; Kayal, Neeraj ; Saxena, Nitin (septiembre de 2004). "PRIMES está en P" (PDF) . Anales de Matemáticas . 160 (2): 781–793. doi : 10.4007/anales.2004.160.781 . JSTOR  3597229. SEÑOR  2123939.

Enlaces externos

• Mathworld: Certificado de Primalidad
• Mathworld: Certificado Pratt
• Mathworld: Certificado Atkin-Goldwasser-Kilian-Morain
• El Glosario Primordial: Certificado de Primalidad
• Vašek Chvátal . Apuntes de clase sobre las pruebas de primalidad de Pratt. Departamento de Ciencias de la Computación. Universidad Rutgers. Versión en PDF en la Universidad Concordia.