Certificado de primalidade

Origem: Wikipédia, a enciclopédia livre.

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 b2 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[editar | editar código-fonte]

O conceito da certificação de primalidade foi historicamente introduzido pelo Certificado de Pratt, concebido por Vaughan Pratt[1] 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;
  • an-1 ≡ 1(mod n)
  • Para cada fator primo q de n-1, isso não é o caso de an-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
  • 485-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 = 22×3×19)
    • 2 (primo conhecido)
    • 3 (a=2, 3−1 = 2)
      • 2 (primo conhecido)
    • 19 (a=2, 19−1 = 2×32)
      • 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 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 p1,...,pk. Pela hipótese indutiva a árvore de raiz em pi contém no máximo valores, então a árvore inteira contém no máximo:

desde que k ≥ 2 e p1...pk = 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[necessário esclarecer] 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[editar | editar código-fonte]

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.[2] 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.[3] 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;
  • Mx,My,A,B em (os inteiros modn) satisfazendo My2 = Mx3 + AMx + B e com 4A3 + 27B2 coprimo de n;
  • um primo .
Então M=(Mx,My) não é um ponto-identidade numa curva elíptica y2 = x3 + 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 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 . 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 Mx, My, 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[editar | editar código-fonte]

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.

Referências

  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
  3. Atkin, A. O. L. and Morain, F. "Elliptic Curves and Primality Proving." Math. Comput. 61, 29-68, 1993. At Citeseer

Ligações externas[editar | editar código-fonte]

Alguns certificados conhecidos.[1]