Teste de primalidade AKS
Origem: Wikipédia, a enciclopédia livre.
O teste da primalidade AKS (também conhecido como teste da primalidade Agrawal-Kayal-Saxena) é um algoritmo prova primalidade determinístico criado e publicado por cientistas Indianos chamados Manindra Agrawal, Neeraj Kayal e Nitin Saxena em 6 de Agosto, 2002 em um trabalho intitulado "PRIMES is in P".
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
Índice |
[editar] Importância
O significado principal do AKS é que ele é o primeiro algoritmo publicado pra 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 numero objetivo, isto nos permite classificar o numero 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)
[editar] Bases do teste
O teste de primalidade AKS é baseado na equivalência:
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: : 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:
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,
Durante este passo, é importante confirmar que n não é divisível por nenhum primo ; 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 campo finito GF(nr), no caso de testar a equivalência de dois polinômios no campo: se : Para todos os inteiros positivos a com : 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(log12 + ε(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(log6 + ε(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.
[editar] Algoritmo
Verificar se um numero N é composto ou primo
Introduzir: Inteiro n > 1 SE (n ESTÁ NA FORMA ab 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 "PRIM0"
[editar] Referências
- ^ Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
- ^ H. W. Lenstra, Jr. and Carl Pomerance, "Primality Testing with Gaussian Periods", preliminary version July 20, 2005.