Ver el código de «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 [[Polinomio|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''<sup>2</sup> bits).

Los certificados de primalidad conducen directamente a demostraciones de que problemas como los [[test de primalidad|tests de primalidad]] y los [[complemento (complejidad)|complementos]] de [[factorización de enteros]] se encuentran en la categoría [[NP (clase de complejidad)|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-completo]]s, 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]],<ref>Vaughan Pratt. "Every prime has a succinct certificate". ''SIAM Journal on Computing'', vol.4, pp.214–220. 1975. [http://citeseer.ist.psu.edu/context/39245/0 Citations], [http://boole.stanford.edu/pub/SucCert.pdf Full-text].</ref> 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 lógica|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''<sup>''n'' − 1</sup> ≡ 1 (modificación ''n''),
:* para todo factor primo ''q'' de ''n'' − 1, no se da el caso de que ''a''<sup>(''n''−1)/''q''</sup> ≡ 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'')<sup>4</sup>); 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'')<sup>3</sup>(log log ''n'')(log log log ''n'')), o usando la [[Cota superior asintótica|notación ''soft-O'']] Õ((log ''n'')<sup>3</sup>).

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<sup>85−1</sup> ≡ 1 (módulo 85),
* 4<sup>(85−1)/6</sup> ≡ 16 (módulo 85), 4<sup>(85−1)/14</sup> ≡ 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<sup>2</sup>×3×19),
** 2 (primo conocido),
** 3 (''a''=2, 3−1 = 2),
*** 2 (primo conocido),
** 19 (''a''=2, 19−1 = 2×3<sup>2</sup>),
*** 2 (primo conocido),
*** 3 (''a''=2, 3−1 = 2),
**** 2 (primo conocido).

Se puede demostrar que este árbol de prueba contiene como máximo <math>4\log_2 n - 4</math> 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''<sub>1</sub>, ..., ''p''<sub>''k''</sub>. Por la hipótesis inductiva, el árbol con raíz en ''p''<sub>''i''</sub> contiene como máximo <math>4\log_2 p_i - 4</math> valores, por lo que todo el árbol contiene como máximo

: <math>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,</math>

ya que ''k'' ≥ 2, y ''p''<sub>1</sub>...''p''<sub>''k''</sub> = ''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'')<sup>2</sup>) 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'')<sup>3</sup> (log log ''n'')(log log log ''n'')), o Õ((log ''n'')<sup>3</sup>), 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úmero de Fermat|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 [[curva elíptica|curvas elípticas]].<ref>Goldwasser, S. and Kilian, J. "Almost All Primes Can Be Quickly Certified". Proc. 18th STOC. pp. 316–329, 1986. [http://groups.csail.mit.edu/cis/pubs/shafi/1986-stoc-gk.pdf Full text].</ref> 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]].<ref name= "atkin-morain">{{cite journal|last1= Atkin|first1= A O.L.|author1-link= A. O. L. Atkin|last2= Morain|first2= F.|doi=  10.1090/s0025-5718-1993-1199989-x|issue= 203|journal= [[Mathematics of Computation]]|mr= 1199989|pages= 29–68|title= Elliptic curves and primality proving|volume= 61|year= 1993|jstor= 2152935|url= https://www.ams.org/mcom/1993-61-203/S0025-5718-1993-1199989-X/S0025-5718-1993-1199989-X.pdf}}</ref> 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<sub>''x''</sub>, M<sub>''y''</sub>, A, B en <math>\mathbb{Z}_n</math> (los enteros mod ''n'') que satisfacen M<sub>''y''</sub><sup>2</sup> = M<sub>''x''</sub><sup>3</sup> + AM<sub>''x''</sub> + B y con 4A<sup>3</sup> + 27B<sup>2</sup> coprimos a ''n'';
:* Un primo <math>q > n^{1/2} + 1 + 2n^{1/4}</math>.
: Entonces M= (M<sub>''x''</sub>, M<sub>''y''</sub>) es un punto de no identidad en la curva elíptica ''y''<sup>2</sup>= ''x''<sup>3</sup> + Ax + B. Sea ''k''M M sumado a sí mismo ''k'' veces usando la suma de curvas elípticas estándar. Entonces, si ''q''M 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 <math>\mathbb{Z}_n</math> 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 <math>\mathbb{Z}_n</math>. 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<sub>''x''</sub>, M<sub>''y''</sub>, 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'')<sup>2</sup>) y se puede verificar en tiempo O((log ''n'')<sup>4</sup>). 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]])<ref name="Pocklington">{{cite journal|first=Henry C.|last=Pocklington|author-link=Henry Cabourn Pocklington|title=The determination of the prime or composite nature of large numbers by Fermat's theorem|journal=Proceedings of the Cambridge Philosophical Society|volume=18|date=1914–1916|pages=29–30}}</ref> 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 <math>P=Rh+1</math> donde <math>R=\prod q_j^{e_j}</math> y <math>q_j</math> son primos distintos, con <math>e_j</math> un entero mayor que cero y un testigo <math>g</math> tal que:

{|
|-
||&nbsp;&nbsp;&nbsp;
||{{NumBlk|:|1. <math>g^{Rh}\equiv 1 \bmod{P}</math>|{{EquationRef|1}}}}
{{NumBlk|:|2. <math>\gcd((g^{Rh/q_j}-1\bmod{P}), P)=1</math> for all <math>q_j</math>.|{{EquationRef|2}}}}
|}

Entonces P es primo si se cumple una de las siguientes condiciones:
{|
|-
||&nbsp;&nbsp;&nbsp;
||
{{NumBlk|:|a) (véase<ref name="Primes">{{cite book|first1=Richard|last1=Crandall|first2=Carl|last2=Pomerance|title="Prime Numbers: A computational perspective"|edition=2|publisher="Springer-Verlag, 175 Fifth Ave, New York, New York 10010, U.S.A., 2005"}}</ref>) <math>R\geq h</math> o equivalentemente <math>R> P^{1/2}</math>|{{EquationRef|a}}}}
{{NumBlk|:|b) (véase<ref name="BLS75">{{cite journal|first1=John|last1=Brillhart|author-link1=John Brillhart|first2=D. H.|last2=Lehmer|author-link2=Derrick Henry Lehmer|first3=J. L.|last3=Selfridge|author-link3=John Selfridge|title=New Primality Criteria and Factorizations of 2<sup>m</sup> ± 1|journal=Mathematics of Computation|volume=29|number=130|date=April 1975|pages=620–647|jstor=2005583|doi=10.1090/S0025-5718-1975-0384673-1|url=https://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf }}</ref>{{rp|Corolario 1}}) <math>R\geq h^{1/2}</math> o equivalentemente <math>R> P^{1/3}</math> y 
* con <math>\begin{array}{lr}a\equiv h\bmod{R} &0\leq a < R\\b=(h-a)/R \end{array}</math>,
* tal que <math>(a-4b)\neq 0</math> y existe un primo pequeño <math>r>2</math> tal que <math>(a-4b)^{r/2}\neq 1\bmod{r}</math>.
|{{EquationRef|b}}}}
|}

=== Certificado de primalidad de Pocklington ===

Un certificado de primalidad de Pocklington consta del primo P, un conjunto de primos <math>q_j</math> que dividen a <math>(P-1)</math>, cada uno con su propio certificado de primalidad de Pocklington o lo suficientemente pequeño como para ser un primo conocido, y un testigo <math>g</math>.

Los bits necesarios para este certificado (y el orden del costo computacional) deben variar desde aproximadamente <math>\log_2{P}\left(1 + \sum_{k=1}^{\infty}\frac{1}{3^k}\right)= 1.5\log_2{P}</math> para la versión ({{EquationNote|b}}) hasta <math>\log_2{P}\left(1 + \sum_{k=1}^{\infty}\frac{1}{2^k}\right)= 2\log_2{P}</math> para la versión ({{EquationNote|a}}).

=== Ejemplo sencillo ===

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

== Impacto de "PRIMES is in P" ==

"PRIMES is in P"<ref name="AKS">{{cite journal|first=Manindra|last=Agrawal|authorlink1=Manindra Agrawal|first2=Neeraj|last2=Kayal|authorlink2=Neeraj Kayal|first3=Nitin|last3=Saxena|authorlink3=Nitin Saxena|url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf|title=PRIMES is in P|journal=[[Annals of Mathematics]]|volume=160|date=September 2004|issue=2|pages=781–793|doi=10.4007/annals.2004.160.781|jstor=3597229|mr=2123939}}</ref> 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'')<sup>6</sup>). 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 ==
{{listaref}}

== Enlaces externos ==
* [http://mathworld.wolfram.com/PrimalityCertificate.html Mathworld: Primality Certificate]
* [http://mathworld.wolfram.com/PrattCertificate.html Mathworld: Pratt Certificate]
* [http://mathworld.wolfram.com/Atkin-Goldwasser-Kilian-MorainCertificate.html Mathworld: Atkin-Goldwasser-Kilian-Morain Certificate]
* [https://primes.utm.edu/glossary/page.php?sort=Certificate The Prime Glossary: Certificate of Primality]
* [[Václav Chvátal]]. [https://web.archive.org/web/20060104210644/http://www.cs.rutgers.edu/~chvatal/notes/ppp/ppp.html Lecture notes on Pratt's Primality Proofs]. Department of Computer Science. Rutgers University. [http://www.cs.concordia.ca/~chvatal/notes/ppp.pdf PDF version at Concordia University].
* Wim van Dam. {{Enlace roto|1=[http://www.cs.ucsb.edu/~vandam/teaching/CS172/pratt.pdf Proof of Pratt's Theorem] |2=http://www.cs.ucsb.edu/~vandam/teaching/CS172/pratt.pdf }} (Enlace roto: marzo de  2018). (Lecture notes, PDF)

{{Control de autoridades}}
[[Categoría:Tests de primalidad| ]]