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² 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)⁴) 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)³(log log n)(log log log n) de tempo, ou usando a notação Õ((log n)³).

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²×3×19)
  • 2 (primo conhecido)
  • 3 (a=2, 3−1 = 2)
    • 2 (primo conhecido)
  • 19 (a=2, 19−1 = 2×3²)
    • 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₁,...,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₁...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)²) 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)³(log log n)(log log log n)) ou Õ((log n)³), 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² = M_x³ + AM_x + B e com 4A³ + 27B² 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² = x³ + 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)²) e pode ser verificado em tempo O((log n)⁴). 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)⁶). 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.

Ligações externas

Alguns certificados conhecidos.

• Mathworld: Primality Certificate
• Mathworld: Pratt Certificate
• Mathworld: Atkin-Goldwasser-Kilian-Morain Certificate
• Vašek 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. (Lecture notes, PDF)