Teste de primalidade AKS

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita uma ou mais fontes fiáveis e independentes, mas ela(s) não cobre(m) todo o texto (desde Dezembro de 2013).
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes e inserindo-as em notas de rodapé ou no corpo do texto, conforme o livro de estilo.
Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.

O teste da primalidade AKS (também conhecido como teste da primalidade Agrawal-Kayal-Saxena) é um algoritmo de teste de primalidade determinístico criado e publicado por cientistas Indianos chamados Manindra Agrawal, Neeraj Kayal e Nitin Saxena em 6 de Agosto de 2002 em um trabalho intitulado "PRIMES is in P".[1]

Os autores receberam o Premio Gödel de 2006 por este trabalho.

O algoritmo, que foi agora melhorado por outros, determina se um número é primo ou composto e roda em tempo polinomial

Importância[editar | editar código-fonte]

O significado principal do AKS é que ele é o primeiro algoritmo publicado para ser simultaneamente polinomial, determinístico, e incondicional. O que isto significa, o tempo máximo de processamento do algoritmo pode ser expresso como um polinômio em relação ao número de dígitos no número objetivo, isto nos permite classificar o número informado como primo o composto (ao invés de retornar um resultado probabilístico); e a sua correção não esta subordinada a exatidão de uma hipótese subsidiária não provada (tal como a hipótese de Riemann)

Bases do teste[editar | editar código-fonte]

O teste de primalidade AKS é baseado na equivalência:

(x - a)^{n} \equiv (x^{n} - a) \pmod{n}

A qual é verdadeira somente se n é primo. Isto é uma generalização do pequeno teorema de Fermat estendido para polinômios e pode ser facilmente provado usando o teorema binomial juntamente com o fato que: :{n \choose k} \equiv 0 \pmod{n} para todo 0 < k < n se n é primo.

Enquanto esta inequação constitui um teste de primalidade por si só, verificando isto em tempo exponencial. Além disto AKS faz uso da relação de equivalência:

(x - a)^{n} \equiv (x^{n} - a) \pmod{n, x^{r} - 1}

a qual pode ser verificada em tempo polinomial. Contudo enquanto todos os primos satisfazem esta equivalência alguns números compostos também o fazem. A prova da correção consiste em mostrar que existe um conveniente menor r e um conveniente conjunto menor de inteiros A tal que se a equivalência que assegura que para todo a em A então n deva ser primo.

O algoritmo para o teste de primalidade de algum inteiro n consiste de duas partes. O primeiro passo gira em torno de encontrar um número primo conveniente r = kq + 1, tal que:

  • P(r - 1) = q onde P(x) é o maior fator primo de x,
  • q \ge 4 \sqrt{r} \log_{2}(n),
  • n^k \not\equiv 1 \pmod{r}.

Durante este passo, é importante confirmar que n não é divisível por nenhum primo p \le r; Se ele é divisível, o algoritmo poderá terminar imediatamente para avisar que n é composto.

No segundo passo, um número de teste são feitos em um corpo finito GF(n^r), no caso de testar a equivalência de dois polinômios no campo: se :(x - a)^{n} \equiv (x^{n} - a) \pmod{n, x^{r} - 1} Para todos os inteiros positivos a com : a \le 2 \sqrt{r} \log_{2}(n), então n é garantidamente primo. Em todos os outros casos ele é composto.

Como em qualquer tipo algoritmo, o estudo em si se preocupa em estabelece dois fatos: provar que o algoritmo esta correto, e estabelecer sue tempo de complexidade assintótico. Isto pode ser encontrado e estabelecido em um limite superior da sua magnitude, e depois pela demonstração que o teste de equidade múltiplo na segunda parte do algoritmo ce suficiente para garantir se n é primo ou composto.

Desde o tempo de processamento de ambas as partes do algoritmo é inteiramente dependente da magnitude de r, provando um limite superior de r foi suficiente para mostrar que o tempo de complexidade assintótico do algoritmo é O(\log^{12+\epsilon}(n)), onde ε é um número pequeno. Em outras palavras, o algoritmo leva menos que uma constante vezes a décima segunda potência (mais ε) do número de dígitos de n.

Contudo o limite superior provado no trabalho é bastante folgado; isto é, um tanto conservador a cerca da distribuição dos números primos de Sophie Germain exibe, se verdadeiro, imediatamente reduziria o pior caso para O(\log^{6+\epsilon}(n)).

Nos meses seguintes a descobertas de novas variantes apareceram (Lenstra 2002, Pomerance 2002, Berrizbeitia 2003, Cheng 2003, Bernstein 2003a/b, Lenstra and Pomerance 2003) as quais melhoraram a velocidades do AKS em várias ordens de magnetude. Devido a existência de muitas variantes, Crandall e Papadopoulos referem-se a classe-AKS de algoritmos em seu trabalhos científico "On the implementation of AKS-class primality tests" publicado em Março de 2003.

Algoritmo[editar | editar código-fonte]

Verificar se um número N é composto ou primo[2]:


Introduzir: Inteiro n > 1

SE (n ESTÁ NA FORMA a^b COM b > 1) ENTÃO mostrar "COMPOSTO"

r := 2
while (r < n) {
    SE (Mdc(n,r) NÃO É 1) ENTÃO mostrar "COMPOSTO"
    SE (r É UM Nº PRIMO MAIOR QUE 2) ENTÃO {
        q = MAIOR FACTOR DE r-1
        SE (q > 4sqrt(r)log n) e (n(r-1)/q NÃO É IGUAL A 1(mod r)) ENTÃO SAIR DESTE CICLO(BREAK)
    }
    r := r+1
}

PARA a = 1  TO 2sqrt(r)log n {
    SE ( (x-a)^n  NÃO É  (x^n-a) (mod x^r-1,n) ) ENTÃO mostrar "COMPOSTO"
}

mostrar ¨PRIMO¨

Um teste elementar e preciso de primalidade[editar | editar código-fonte]

Sabe-se que, com exceção dos números 2 e 3, todos os outros números primos são expressos pela fórmula Ip=6K±1, mas se sabe também que a imensa maioria dos números expresso pela fórmula Ip=6K±1 não são primos.

O estudo dos números não-primos da forma Ip=6K±1 nos leva a igualdade

K = 6k2k3±k2±k3

Dado um número qualquer K inteiro,positivo, se não ocorrer nenhum par de números inteiros positivos k2,k3 que satisfaça a igualdade acima, afirma-se que os números Ip=6K±1 são primos gêmeos. Se não ocorrer nenhum par de números k2,k3 com sinais iguais que satisfaça a igualdade e ocorrer ao menos um par de números k2,k3 com sinais diferentes que satisfaça a igualdade para um determinado valor de K afirma-se que Ip=6K+1 é primo e Ip=6K-1 não é primo. Se não ocorrer nenhum par de números k2,k3 com sinais diferentes que satisfaça a igualdade e ocorrer ao menos um par de números k2,k3 com sinais iguais que satisfaça a igualdade para um determinado valor de K afirma-se que Ip=6K-1 é primo e Ip=6K+1 não é primo.

Referências[editar | editar código-fonte]

  1. Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
  2. H. W. Lenstra, Jr. and Carl Pomerance, "Primality Testing with Gaussian Periods", preliminary version July 20, 2005.
  3. Bruno da Rocha Braga, "Implementando o Algoritmo AKS para Primalidade de um Número em Tempo Polinomial", laboratório Ravel/Coppe/UFRJ, 11 de setembro de 2002.

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