Certificado de primalidad

En matemáticas y ciencias de la computación, un certificado de primalidad, prueba de primalidad o certeza de primalidad es una prueba formal y sucinta de que un número es primo. Los certificados de primalidad permiten verificar rápidamente la primalidad de un número sin tener que ejecutar un test de primalidad costoso o poco fiable. "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 b² bits).

Los certificados de primalidad conducen directamente a demostraciones de que problemas como los tests de primalidad y los complementos de factorización de enteros se encuentran en la categoría NP, la clase de problemas verificables en tiempo polinomial dada una solución. Estos problemas ya se encuentran trivialmente en la categoría 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, fue la primera demostración de un problema en NP intersección con 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 estándar de primalidad probabilística como el test de primalidad Baillie-PSW, el test de primalidad de Fermat y el test 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 primas.

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

Teorema de Lucas': Supóngase que se tiene un entero a tal que:

a^{n − 1} ≡ 1 (modificación n),
para todo factor primo q de n − 1, no se da el caso de que a^{(n − 1)/q} ≡ 1 (mod n).

Entonces n es primo.

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). Incluso con la multiplicación de enteros de la escuela primaria, esto solo supone un tiempo proporcional a O((log n)⁴); usando el algoritmo de multiplicación con el tiempo de ejecución asintótico más conocido, el algoritmo de Schönhage-Strassen, puede reducirse a O((log n)³(log log n)(log log log n)), o usando la [[Cota superior asintótica|notación soft-O]] Õ((log n)³).

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. Por ejemplo, supóngase que se afirma que n = 85 es primo, proporcionando a = 4 y n − 1 = 6 × 14 como su factorización prima. Entonces (usando q = 6 y q = 14):

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

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:

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 $4\log _{2}n-4$ 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, tómese p > 3 y 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 $4\log _{2}p_{i}-4$ valores, por lo que todo el árbol contiene como máximo

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,

ya 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 verificar (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)³), que es bastante factible para números en el rango en el que los teóricos de números computacionales suelen trabajar.

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.

Certificados de Atkin-Goldwasser-Kilian-Morain

Para abordar el problema de la generación eficiente de certificados para números más grandes, en 1986 Shafrira Goldwasser y Joe Kilian describieron un nuevo tipo de certificado basado en la teoría de las curvas elípticas.[2] A su vez, fue utilizado por A. 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"):

Teorema: Supóngase que se reciben:

Un entero positivo n no divisible por 2 o 3;
M_x, M_y, A, B en $\mathbb {Z} _{n}$ (los enteros mod n) que satisfacen M_y² = M_x³ + AM_x + B y con 4A³ + 27B² coprimos a n;
Un primo $q>n^{1/2}+1+2n^{1/4}$ .

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

Técnicamente, una curva elíptica solo se puede construir sobre un cuerpo, y $\mathbb {Z} _{n}$ solo es un cuerpo si n es primo, por lo que parece que se asume el resultado que se está tratando de probar. La dificultad surge en el algoritmo de suma de curvas elípticas, que toma inversas en el campo que pueden no existir en $\mathbb {Z} _{n}$ . 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 M_x, M_y, 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)²) y se puede verificar en tiempo O((log n)⁴). 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.

Certificados basados en el teorema de Pocklington

La generación de primos demostrables basada en variantes del teorema de Pocklington (véase test de Pocklington-Lehmer)[4] permite obtener técnicas eficientes para generar primos (el costo es generalmente menor que la generación probabilística) con el beneficio adicional de certificados de primalidad integrados. 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.

Pruebas de primalidad de Pocklington

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

1. $g^{Rh}\equiv 1{\bmod {P}}$

(1)

2. $\gcd((g^{Rh/q_{j}}-1{\bmod {P}}),P)=1$ for all $q_{j}$ .

(2)

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

a) (véase [5]) $R\geq h$ o equivalentemente $R>P^{1/2}$

(a)

b) (véase [6]^{: Corolario 1}) $R\geq h^{1/2}$ o equivalentemente $R>P^{1/3}$ y

con ${\begin{array}{lr}a\equiv h{\bmod {R}}&0\leq a<R\\b=(h-a)/R\end{array}}$ ,
tal que $(a-4b)\neq 0$ y existe un primo pequeño $r>2$ tal que $(a-4b)^{r/2}\neq 1{\bmod {r}}$ .

(b)

Certificado de primalidad de Pocklington

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

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

Ejemplo sencillo

Sea $P=1056893$ . Téngase en cuenta que $(P-1)=1621\cdot 163\cdot 2^{2}$ y que $P^{1/2}=1028.053\ldots$ , $P^{1/3}=101.86156\ldots$ .

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

Impacto de "PRIMES is in 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 polinomial. Los autores recibieron el Premio Gödel de 2006 y el Premio Fulkerson de 2006 por este trabajo.

Debido a que la prueba de primalidad ahora se puede realizar de manera determinista en tiempo polinomial utilizando el test de primalidad AKS, un número primo en sí mismo podría considerarse un certificado de su propia primalidad. Esta prueba se ejecuta en tiempo Õ((log n)⁶). 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.

Referencias

Vaughan Pratt. "Every prime has a succinct certificate". SIAM Journal on Computing, vol. 4, pp. 214–220. 1975. Citations, Full-text.
Goldwasser, S. and Kilian, J. "Almost All Primes Can Be Quickly Certified". Proc. 18th STOC. pp. 316–329, 1986. Full text.
Atkin, A O.L.; Morain, F. (1993). «Elliptic curves and primality proving». Mathematics of Computation 61 (203): 29-68. JSTOR 2152935. MR 1199989. doi:10.1090/s0025-5718-1993-1199989-x.
Pocklington, Henry C. (1914–1916). «The determination of the prime or composite nature of large numbers by Fermat's theorem». Proceedings of the Cambridge Philosophical Society 18: 29-30.
Crandall, Richard; Pomerance, Carl. "Prime Numbers: A computational perspective" (2 edición). "Springer-Verlag, 175 Fifth Ave, New York, New York 10010, U.S.A., 2005".
Brillhart, John; Lehmer, D. H.; Selfridge, J. L. (April 1975). «New Primality Criteria and Factorizations of 2^m ± 1». Mathematics of Computation 29 (130): 620-647. JSTOR 2005583. doi:10.1090/S0025-5718-1975-0384673-1.
Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (September 2004). «PRIMES is in P». Annals of Mathematics 160 (2): 781-793. JSTOR 3597229. MR 2123939. doi:10.4007/annals.2004.160.781.

Enlaces externos

Mathworld: Primality Certificate
Mathworld: Pratt Certificate
Mathworld: Atkin-Goldwasser-Kilian-Morain Certificate
The Prime Glossary: Certificate of Primality
Václav Chvátal. Lecture notes on Pratt's Primality Proofs. Department of Computer Science. Rutgers University. PDF version at Concordia University.
Wim van Dam. Proof of Pratt's Theorem (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). (Enlace roto: marzo de 2018). (Lecture notes, PDF)

Datos: Q7243047

Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.

[1] Vaughan Pratt. "Every prime has a succinct certificate". SIAM Journal on Computing, vol. 4, pp. 214–220. 1975. Citations, Full-text.

[2] Goldwasser, S. and Kilian, J. "Almost All Primes Can Be Quickly Certified". Proc. 18th STOC. pp. 316–329, 1986. Full text.

[atkin-morain-3] Atkin, A O.L.; Morain, F. (1993). «Elliptic curves and primality proving». Mathematics of Computation 61 (203): 29-68. JSTOR 2152935. MR 1199989. doi:10.1090/s0025-5718-1993-1199989-x.

[Pocklington-4] Pocklington, Henry C. (1914–1916). «The determination of the prime or composite nature of large numbers by Fermat's theorem». Proceedings of the Cambridge Philosophical Society 18: 29-30.

[Primes-5] Crandall, Richard; Pomerance, Carl. "Prime Numbers: A computational perspective" (2 edición). "Springer-Verlag, 175 Fifth Ave, New York, New York 10010, U.S.A., 2005".

[BLS75-6] Brillhart, John; Lehmer, D. H.; Selfridge, J. L. (April 1975). «New Primality Criteria and Factorizations of 2^m ± 1». Mathematics of Computation 29 (130): 620-647. JSTOR 2005583. doi:10.1090/S0025-5718-1975-0384673-1.

[AKS-7] Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (September 2004). «PRIMES is in P». Annals of Mathematics 160 (2): 781-793. JSTOR 3597229. MR 2123939. doi:10.4007/annals.2004.160.781.