# Teste de primalidade AKS

O teste de primalidade AKS (também conhecido como teste de 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".
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

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 ou 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

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\geq 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\leq 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\leq 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

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

### Um teste elementar e preciso de primalidade

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\pm 1$ mas se sabe também que a imensa maioria dos números expresso pela fórmula $Ip=6K\pm 1$ não são primos.
Os números compostos da forma $Ip=6K\pm 1$ são obtidos pela multiplicação de dois números da forma $Ip=6K\pm 1$onde estes dois números podem ser ambos primos ou ambos compostos e também ser o produto de um número primo por um número compostos como vemos abaixo:
$6K\pm 1=(6K_{2}\pm 1).(6K_{3}\pm 1)=6.6K_{2}.K_{3}\pm 6K_{2}.1\pm 6K_{3}.1\pm 1$que podemos escrever
$6K\pm 1=6(6K_{2}.6K_{3}\mp K_{2}\pm K_{3})\pm 1$
Vemos então que esta igualdade só existe se
$K=6K_{2}K_{3}\pm K_{2}\pm K_{3}$
Se esta igualdade não existir para sinais iguais ou diferentes, então o par de números $6K\pm 1$ não existe como números compostos, logo o par de números $6K\pm 1$ serão números primos gêmeos.
Então dado um número qualquer $K$ inteiro,positivo, se não ocorrer nenhum par de números inteiros positivos $K_{2},K_{3}$ que satisfaça a igualdade acima, afirma-se que os números $I_{p}=6K\pm 1$ são primos gêmeos.
Se não ocorrer nenhum par de números $K_{2},K_{3}$ com sinais iguais que satisfaça a igualdade e ocorrer ao menos um par de números $K_{2},K_{3}$ com sinais diferentes que satisfaça a igualdade para um determinado valor de $K$ afirma-se que $I_{p}=6K+1$ é primo e $I_{p}=6K-1$ não é primo.
Se não ocorrer nenhum par de números $K_{2},K_{3}$ com sinais diferentes que satisfaça a igualdade e ocorrer ao menos um par de números $K_{2},K_{3}$ com sinais iguais que satisfaça a igualdade para um determinado valor de $K$ afirma-se que $I_{p}=6K-1$ é primo e $I_{p}=6K+1$ não é primo.