O algoritmo AKS para reconhecimento de números primos

Resumo: O reconhecimento de números primos é um problema matemático clássico, e especialmente curioso do ponto de vista computacional por ser talvez o mais famoso exemplo em NP inter co-NP. Para muitos efeitos práticos, o problema já está faz tempo em P; o algoritmo de Miller resolve isso, a menos de um "pequeno" detalhe.

Recentemente, Agarwal, Kayal e Saxena apresentaram um algoritmo que decide se um número dado é primo em tempo polinomial. O algoritmo é simples, entretanto, tanto a complexidade como a corretude são não triviais, e dependem mais de Teoria dos Números do que de técnicas computacionais. Um fato que surpreendeu a muitos especialistas é que o grau de sofisticação das ferramentas utilizadas é bem baixo, dentro do panorama atual da Teoria dos Números.

Pretendo apresentar o algoritmo e sua análise, bem como sua relação com o algoritmo de Miller.