Certificat de primalidad

En matemàtiques i ciències de la computació, un certificat de primalidad, prova de primalidad o certea de primalidad és una prova formal i sucinta de que un número és primer. Els certificats de primalidad permeten verificar ràpidament la primalidad d'un número sense tindre que eixecutar un test de primalidad costós o poc fiable. "Sucinta" generalment significa que la prova deu ser com a màxim polinòmica, en una cantitat de dígits no desmesuradamente major que número en sí (per eixemple, si el número té b bits, la prova pot contindre aproximadament b² bits).

Els certificats de primalidad conduïxen directament a demostracions de que problemes com els tests de primalidad i els complements de factorización de sancers es troben en la categoria NP, la classe de problemes verificables en temps polinomial donada una solució. Estos problemes ya es troben trivialmente en la categoria co-NP. Esta va ser la primera evidència sòlida de que estos problemes no són NP-complets, ya que si ho anaren, implicaria que NP és un subconjunt de co-NP, un resultat que es creu que és fals; de fet, va ser la primera demostració d'un problema en NP intersecció en co-NP que, en eixe moment, no se sabia que estava en P.

Produir certificats per al problema del complement, per a establir que un número és compost, és senzill: n'hi ha prou en donar un divisor no trivial. Les proves estàndar de primalidad provabilística com el test de primalidad Baillie-PSW, el test de primalidad de Fermat i el test de primalidad de Miller-Rabin també produïxen certificats de composició en el cas de que l'entrada siga composta, pero no produïxen certificats per a entrades primeres.

Certificats Pratt

El concepte de certificats de primalidad va ser introduït històricament pel certificat Pratt, concebut en 1975 per Vaughan Pratt, qui va descriure la seua estructura i va demostrar que tenia tamany polinomial i que era verificable en temps polinomial. Es basa en el test de Lucas, que és essencialment la conversió del menuda teorema de Fermat en una condició adicional per a que siga cert:

Teorema de Lucas': Suponga's que es té un sancer a tal que:

• a^{n − 1} ≡ 1 (modificació n),
• per a tot factor primer q de n − 1, no es dona el cas de que a^(n−1)/q ≡ 1 (mod n).

Llavors n és primer.

Dau tal a (cridat testic) i la descomposició en factors primers de n−1, és simple verificar ràpidament les condicions anteriors: solament es necessita fer un número llineal de exponenciaciones modular, ya que cada número entero té menys factors primers que bits, i cada u d'estos pot fer-se per mig d'exponenciación binaria en O(log n) multiplicacions (vore cota superior asintòtica). Inclús en la multiplicació de sancers de l'escola primària, açò solament supon un temps proporcional a O((log n)⁴); usant l'algoritme de multiplicació en el temps d'eixecució asintòtic més conegut, l'algoritme de Schönhage-Strassen, pot reduir-se a O((log n)³(log log n)(log log log n)), o usant la notació soft-O Õ((log n)³).

No obstant, és possible enganyar a un criteri verificador per a que accepte un número compuesto donant-li una "factorización primera" de n−1 que incloga número compuesto. Per eixemple, suponga's que s'afirma que n=85 és primer, proporcionant a=4 i n−1=6×14 com la seua factorización primera. Llavors (usant q=6 i q=14):

• 4 és coprimo de 85,
• 4⁸⁵⁻¹ ≡ 1 (mòdul 85),
• 4^(85−1)/6 ≡ 16 (mòdul 85), 4^(85−1)/14 ≡ 16 (mòdul 85).

Es conclouria falsament que 85 és primer. No es desija simplement obligar al verificador a factorizar el número, per lo que una millor manera d'evitar este problema és otorgar certificats de primalidad per a cada u dels factors primers de n−1 també, que són solament instàncies més chicotetes del problema original. Llavors, es continua recursivamente d'esta manera fins a aplegar a un número primo, com 2. Finalment, s'obté un arbre d'número primo, cada u associat en un testic a. Per eixemple, a continuació s'inclou un certificat complet de Pratt per al número 229:

• 229 (a=6, 229−1 = 2²×3×19),
  • 2 (primer conegut),
  • 3 (a=2, 3−1 = 2),
    • 2 (primer conegut),
  • 19 (a=2, 19−1 = 2×3²),
    • 2 (primer conegut),
    • 3 (a=2, 3−1 = 2),
      • 2 (primer conegut).

Es pot demostrar que este arbre de prova conté com a màxim $4{\log }_{2}n-4$ valors distints de 2 per mig d'una prova inductiva simple (basada en la teorema 2 de Pratt). El resultat és vàlit per a 3; en general, prenga's p > 3 i que els seus fills en l'arbre siguen p₁, ..., p_k. Per l'hipòtesis inductiva, l'arbre en raïl en p_i conté com a màxim $4{\log }_2{p}_i-4$ valors, per lo que tot l'arbre conté com a màxim

$1+\sum _{i=1}^k(4{\log }_2{p}_i-4)=-4k+4{\log }_2{p}_1\cdots p_k\le 4{\log }_{2}p-4,$

ya que k ≥ 2, i p₁...p_k = p− 1. Ya que cada valor té com a màxim (log n) bits, açò també demostra que el certificat té un tamany d'O((log n)²) bits.

Ya que hi ha O(log n) valors distints de 2, i cada u requerix com a màxim una exponenciación per a verificar (i les exponenciaciones dominen el temps d'eixecució), el temps total és O((log n)³ (log log n)(log log log n)), o Õ((log n)³), que és prou factible per a números en el ranc en el que els teòrics de números computacionals solen treballar.

No obstant, encara que en teoria és útil i fàcil de verificar, generar un certificat de Pratt per a n requerix factorizar n−1 i atres números potencialment grans. Açò és simple per a alguns números especials com els números de Fermat, pero actualment és molt més difícil que una simple prova de primalidad per a número primo grans de forma general.

Certificats de Atkin-Goldwasser-Kilian-Morain

Per a abordar el problema de la generació eficient de certificats per a números més grans, en 1986 Shafrira Goldwasser i Joe Kilian varen descriure un nou tipo de certificat basat en la teoria de les curves elíptiques. A la seua volta, va ser utilisat per A. O. L. Atkin i François Morain com a base per als certificats Atkin-Goldwasser-Kilian-Morain, que són el tipo de certificats generats i verificats pels sistemes prova de primalidad de curva elíptica. Aixina com els certificats de Pratt es basen en la teorema de Lucas, els certificats de Atkin-Goldwasser-Kilian-Morain es basen en la següent teorema de Goldwasser i Kilian (lema 2 de "Casi tots els número primo es poden certificar ràpidament"):

Teorema: Suponga's que es reben:

• Un sancer positiu n no divisible per 2 o 3;
• M_x, M_i, A, B en ${\mathbb{Z}}_n$ (els sancers mod n) que satisfan M_i² = M_x³ + AM_x + B i en 4A³ + 27B² coprimos a n;
• Un primer $q>n^{1/2}+1+2n^{1/4}$.

Llavors M= (M_x, M_i) és un punt de no identitat en la curva elíptica i²= x³ + Ax + B. Siga kM M sumat a sí mateixa k voltes usant la suma de curves elíptiques estàndar. Llavors, si qM és l'element d'identitat I, es verifica que n és primer.

Tècnicament, una curva elíptica solament es pot construir sobre un cos, i ${\mathbb{Z}}_n$ solament és un cos si n és primer, per lo que sembla que s'assumix el resultat que s'està tractant de provar. La dificultat sorgix en l'algoritme de suma de curves elíptiques, que pren inverses en el camp que poden no existir en ${\mathbb{Z}}_n$. No obstant, es pot demostrar (lema 1 de "Casi tots els número primo es poden certificar ràpidament") que si simplement es realisen càlculs com si la curva estiguera ben definida i en cap moment s'intenta invertir un element sense invers, el resultat seguix sent vàlit; si apareix un element sense invers, llavors açò significa que n és compost.

Per a deduir un certificat d'esta teorema, primer es codifiquen M_x, M_i, A, B i q, després es codifica recursivamente la prova de primalidad per a q < n, continuant fins a aplegar a un primer conegut. Este certificat té tamany O((log n)²) i es pot verificar en temps O((log n)⁴). Ademés, es pot demostrar que l'algoritme que genera estos certificats és el temps polinomial esperat per a tots menys una chicoteta fracció d'número primo, i esta fracció disminuïx exponencialment en el tamany dels número primo. En conseqüència, és adequat per a generar grans número primo aleatoris certificats, un us que és important en les aplicacions de criptografia, com la generació de claus RSA comprobablemente vàlides.