Mostrar código-fonte de Teste de primalidade AKS

{{mais-notas|data=Dezembro de 2013}}
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".{{ref|AKS2004}}

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 é [[número primo|primo]] ou [[número composto|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]]:
:<math>(x - a)^{n} \equiv (x^{n} - a) \pmod{n}</math>
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: :<math>{n \choose k} \equiv 0 \pmod{n}</math> 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]]:

<math>(x - a)^{n} \equiv (x^{n} - a) \pmod{n, x^{r} - 1}</math>

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 <math>r = kq + 1</math>, tal que:
* <math>P(r - 1) = q</math> onde <math>P(x)</math> é o maior [[fator primo]] de <math>x</math>,
* <math>q \ge 4 \sqrt{r} \log_{2}(n),</math>
* <math>n^k \not\equiv 1 \pmod{r}.</math>
Durante este passo, é importante confirmar que ''n'' não é divisível por nenhum primo <math>p \le r</math>;  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]] <math>GF(n^r)</math>, no caso de testar a equivalência de dois [[polinômio]]s no campo: se :<math>(x - a)^{n} \equiv (x^{n} - a) \pmod{n, x^{r} - 1}</math>
Para todos os inteiros positivos ''a'' com :<math> a \le 2 \sqrt{r} \log_{2}(n),</math> 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 é [[Big O notation|O]]<math>(\log^{12+\epsilon}(n))</math>, 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úmero primo de Sophie Germain|números primos de Sophie Germain]] exibe, se verdadeiro, imediatamente reduziria o pior caso para O<math>(\log^{6+\epsilon}(n))</math>.

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{{ref|BB2002}}:

<pre>

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¨

</pre>

=== Um teste elementar e preciso de primalidade<!-- este "teste elementar" também é citado no teste de primalidade de Fermat. Tem que ver se é necessário essa redundância ou se esse exemplo é necessário aqui no artigo. --> ===
Sabe-se que, com exceção dos números 2 e 3, todos os outros números primos são expressos pela fórmula   <math>Ip=6K\pm1</math>  mas se sabe também que a imensa maioria dos números expresso pela fórmula  <math>Ip=6K\pm1</math> não são primos.

Os  números compostos  da forma <math>Ip=6K\pm1</math> são obtidos pela multiplicação de dois números da forma <math>Ip=6K\pm1</math>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: 

<math>6K\pm1=(6 K_2\pm1).(6K_3\pm1)=6.6K_2.K_3\pm6K_2.1\pm6K_3.1\pm1</math>que podemos escrever

<math>6K\pm1=6(6K_2.6K_3\mp K_2\pm K_3  )\pm1</math> 

Vemos então que esta igualdade só existe se 

<math>K=6K_2K_3\pm K_2\pm K_3</math> 

Se esta igualdade não existir para sinais iguais ou diferentes, então o par de  números <math>6K\pm1</math> não existe como números compostos, logo o par de números <math>6K\pm1 </math> serão [[Números primos gémeos|números primos gêmeos]].  



Então dado um número qualquer <math>K</math> inteiro,positivo, se não ocorrer nenhum par de números inteiros positivos  <math>K_2,K_3</math>  que satisfaça a igualdade acima, afirma-se que os números <math>I_p=6K\pm1</math>  são primos gêmeos.

Se não ocorrer nenhum par de números <math>K_2,K_3</math>  com sinais iguais que satisfaça a igualdade e ocorrer ao menos um par de números <math>K_2,K_3</math>  com sinais diferentes  que satisfaça a igualdade para um determinado valor de <math>K</math> afirma-se que <math>I_p=6K+1</math>  é primo e <math>I_p=6K-1</math>  não é primo.

Se não ocorrer nenhum par de números <math>K_2,K_3</math>  com sinais diferentes que satisfaça a igualdade e ocorrer ao menos um par de números <math>K_2,K_3</math>  com sinais iguais que satisfaça a igualdade para um determinado valor de <math>K</math> afirma-se que <math>I_p=6K-1</math> é primo e <math>I_p=6K+1</math>  não é primo.

== Referências ==
# {{note|AKS2004}}[[Manindra Agrawal]], [[Neeraj Kayal]], [[Nitin Saxena]], [http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf "PRIMES is in P"], ''Annals of Mathematics'' 160 (2004), no. 2, pp.&nbsp;781–793.
# {{note|LP2005}}H. W. [[Lenstra]], Jr. and [[Carl Pomerance]], [http://www.math.dartmouth.edu/~carlp/PDF/complexity12.pdf "Primality Testing with Gaussian Periods"], preliminary version July 20, 2005.
# {{note|BB2002}} Bruno da Rocha Braga, [http://www.lockabit.coppe.ufrj.br/downloads/academicos/aks.pdf "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 ==
* {{Link||2=http://gpoulose.home.att.net/gc/src/AKS_cpp.txt |3=Algoritmo AKS reescrito em C++}}

{{Portal3|Matemática|Tecnologias de informação}}
{{Teoria dos números}}

{{DEFAULTSORT:Teste Primalidade Aks}}
[[Categoria:Testes de primalidade]]
[[Categoria:Algoritmos matemáticos]]