Certificado de primalidade
# Certificado de primalidade

Na Ciência da Computação e na Matemática, o certificado de primalidade ou a prova de primalidade é uma prova sucinta e formal de que um número é primo. Certificados de primalidade permitem de maneira rápida checar a a primalidade de um número, sem ter que rodar um custoso e de difícil compreensão teste de primalidade. Por "sucinta" se quer referir ao que desejamos: que a prova seja no máximo polinomialmente maior que o número de dígitos do próprio número (por exemplo, se um número tem b bits, então a prova deve conter cerca de b$^2$ bits).
Certificados de primalidade conduzem diretamente a provas de que problemas como teste de primalidade e o complemento da fatoração de inteiros estarem na classe NP, a classe de problemas verificáveis em tempo polinomial dada uma determinada solução. Esses problemas já trivialmente estão em co-NP. Essa foi a primeira forte evidência para concluir que esses problemas não são NP-completos, pois se eles estivessem implicaria em NP = co-NP, um resultado que acredita-se ser falso. De fato, esta foi a primeira demonstração de um problema da classe NP que intersecta co-NP, não conhecida (até hoje), para a classe P.
Produzir certificados para o problema do complemento, para estabelecer que um certo número é composto, é simples; se resume a dar um divisor não trivial. Padrões probabilísticos de testes de primalidade tais como o teste de primalidade de Fermat e o teste de primalidade de Miller-Rabin também produzem certificados para os números compostos quando a entrada também é composta, mas não produz certificados para entradas quando estas são primos.

## Certificados de Pratt

O conceito da certificação de primalidade foi historicamente introduzido pelo Certificado de Pratt, concebido por Vaughan Pratt em 1975, que descreveu sua estrutura e provou ter tamanho polinomial e verificação em tempo polinomial. O certificado foi baseado no Teste de primalidade de Lucas, que é essencialmente uma conversão do Pequeno teorema de Fermat com o acréscimo de uma condição para tornar isto verdadeiro:
    Suponha que nós temos um inteiro a como este:
   * a é coprimo de n;
   * a$^{n-1}$ ≡ 1(mod n)
   * Para cada fator primo q de n-1, isso não é o caso de a$^{n-1/q}$ ≡ 1(mode n)
   * Então, n é primo.
Dados um a (chamado de "testemunha") e o primo de fatoração n-1, é simples verificar as condições acima rapidamente: nós apenas precisaremos fazer um número linear de exponenciações modulares, desde que cada inteiro tenha menos fatores primos que bits, e cada um destes possam ser feitos/obtidos por uma exponenciação quadrática em O(log n) multiplicações (ver notação big-O). Mesmo com essa escala de multiplicação de inteiros, isso é apenas O((log n)$^4$) do tempo; usando o algoritmo de multiplicação com o melhor tempo de execução assintótico conhecido, o Algoritmo de Schönhage–Strassen, nós podemos reduzir isso para O((logn)$^3$(log log n)(log log log n) de tempo, ou usando a notação Õ((log n)$^3$).
No entanto, é possível fazer um truque para enganar o verificador, fazendo-o aceitar um número composto dando-lhe o "primo de fatoração" do n-1 que inclui os números compostos. Por exemplo, suponha que afirmamos que n= 85 é primo, fornecendo a = 4 e n- = 6x14 como "primo de fatoração". Então usando q = 6 e q = 14:
* 4 é coprimo de 85
* 4$^{85-1}$ ≡ 1 (mod 85)
* 4$^{(85-1)/6}$ ≡ 16 (mod 85), 4$^{(85−1)/14}$ ≡ 16 (mod 85)
Nós poderíamos falsamente concluir que 85 é primo. Nós não queremos forçar o verificador a fatorar um número então o melhor caminho é escapar desse caso é dar um certificado de primalidade para um dos fatores primos de n-1, que são apenas instâncias menores do problema original. Nós continuamos recursivamente deste maneira até nós atingirmos um número primo conhecido, como 2 por exemplo. Nós terminamos com uma árvore de números primos, cada um associado com uma "testemunha" a. Por exemplo, aqui está o certificado completo de Pratt para o número 229:
* 229 (a=6, 229−1 = 2$^2$×3×19)
** 2 (primo conhecido)
** 3 (a=2, 3−1 = 2)
*** 2 (primo conhecido)
** 19 (a=2, 19−1 = 2×3$^2$)
*** 2 (primo conhecido)
*** 3 (a=2, 3−1 = 2)
**** 2 (primo conhecido)
Através árvore de prova pode-se mostrar que ela contém no máximo $4\log _{2}n-4$ valores diferentes de 2, por uma simples prova indutiva(baseado no 2º Teorema de Pratt). O resultado é valido para 3, em geral, tome p > 3 e deixe seus filhos na árvore serem p$_1$,...,p$_k$. Pela hipótese indutiva a árvore de raiz em p$_i$ contém no máximo $4\log _{2}p_{i}-4$ valores, então a árvore inteira contém no 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,$
desde que k ≥ 2 e p$_1$...p$_k$ = p−1. Cada valor tem no máximo log n bits, isso também demonstra que o certificado tem tamanho de O((log n)$^2$) bits.
Desde que eles sejam O(log n) valores diferentes de 2 e cada um requer no máximo uma exponenciação para verificar (e as exponenciações dominam o tempo de execução), o tempo total é O((log n)$^3$(log log n)(log log log n)) ou Õ((log n)$^3$), que é bastante viável para números na gama computacional, teóricos number geralmente trabalham com ele.
Entretanto, tão útil na teoria e de fácil verificação, realmente gerar um certificado de Pratt para n requer fatorar n-1 e outros números potencialmente grandes. Isso é simples para alguns números especiais como os primos de Fermat, mas comumente muito mais difícil que um simples teste de primalidade para grandes primos de forma geral.

## Certificados de Atkin–Goldwasser–Kilian–Morain

Para tratar do problema da geração de certificados eficientemente para grandes números, em 1986 Shafi Goldwasser e Joe Kilian descreveram um novo tipo de certificado baseado na teoria das curvas elípticas. Isso foi por sua vez utilizado por Arthur Oliver Lonsdale Atkin e François Morain para a base do Certificado Atkin-Goldwasser-Kilian-Morain, que são os tipos de certificados gerados e verificados por sistemas de provas de primalidade por curvas elípticas. Assim como os certificados de Pratt são baseados no teorema de Lehmer's, o certificado de Atkin-Goldwasser-Kilian-Morain é baseado seguindo o teorema de Goldwasser e Kilian(Lemma 2 de "Almost All Primes CAn Be Quickly Crtified"):
    Teorema: Suponha que temos:
   * um inteiro positivo n não divisível por 2 ou 3;
   * M$_x$,M$_y$,A,B em $\mathbb {Z} _{n}$ (os inteiros modn) satisfazendo M$_y$$^2$ = M$_x$$^3$ + AM$_x$ + B e com 4A$^3$ + 27B$^2$ coprimo de n;
   * um primo $q>n^{1/2}+1+2n^{1/4}$.
    Então M=(M$_x$,M$_y$) não é um ponto-identidade numa curva elíptica y$^2$ = x$^3$ + Ax + B. Deixe kM ser M adicionado ele mesmo k vezes usando o padrão de adição da curva elíptica. Então, se qM é o elemento identidade I, então n é primo.
Tecnicamente, uma curva elíptica só pode ser construída sobre um corpo, e $\mathbb {Z} _{n}$ só é um corpo se n é primo, então parecem ser os resultados que estamos tentando provar. A dificuldade surge no algoritmo de adição de uma curva elíptica, que toma inversas no corpo que podem não existir em $\mathbb {Z} _{n}$. No entanto, isto pode ser mostrado (Lemma 1 de "Almost All Primes Can Be Quickly Certified") que se nós apenas executarmos computações sobre curvas que são bem definidas e não para qualquer tentativa de ponto para inverter um elemento que não tem inversa, o resultado permanece válido; se nós encontrarmos um elemento sem inversa, isso determina que n é composto.
Para concluir um certificado partindo desse teorema, nós primeiro codificamos M$_x$, M$_y$, A, B, e q, então recursivamente codificamos a prova da primalidade para q < n, continuando até que atingimos um número primo conhecido. Esse certificado tem tamanho de O((log n)$^2$) e pode ser verificado em tempo O((log n)$^4$). Além disso, pode-se mostrar que o algoritmo que gera estes certificados tem expectativa de tempo polinomial para todos, mas para uma pequena fração dos primos, e essa fração diminui exponencialmente como o tamanho dos números primos. Consequentemente é bem adequado gerar certificado para grandes e aleatórios números primos, uma implicação que é importante para aplicações na área da criptografia como a geração comprovada de chaves RSA.

## Impacto dos primos em P

Devido ao fato de que testar primalidade pode agora ser feito deterministicamente em tempo polinomial usando o teste de primalidade AKS, um número primo pode por si só ser considerado um certificado, o próprio certificado da sua primalidade. Este teste executa em Õ((log n)$^6$). Na prática esse método de verificação é mais caro que a verificação para o certificado de Pratt, mas não requer nenhuma computação para determinar o certificado.