Acesso rápido


Primalidade em tempo polinomial:
uma introdução ao algoritmo AKS

capaDeterminar se um dado número é primo é um problema que remonta à antigüidade grega, quando o matemático Eratóstenes propôs o seu crivo, que ensinamos até hoje na escola.  Vários métodos para testar a primalidade de um número foram inventados no século XIX, em especial por Eduard Lucas (que também criou o conhecido jogo das torres de Hanói).  Apesar disto, este problema só foi sistematicamente abordado a partir da segunda metade do século XX, com o desenvolvimento dos computadores e dos métodos de criptografia de chave pública.  Entretanto, por mais de 30 anos, todos os testes de primalidade inventados eram "lentos"--no sentido técnico de serem algoritmos não polinomiais.  Em 2002 os matemátcos indianos Akrawal, Kayal e Saxena surpreenderam a todos apresentando um algoritmo "rápido" (polinomial, no jargão da teoria de complexidade de algoritmos) que é, ao mesmo tempo, fácil de compreender e implementar. Este livro tem por finalidade descrever  o algoritmo AKS (= Akrawal, Kayal e Saxena)  em detalhes, assumindo pré-requisitos equivalentes ao conteúdo de Números inteiros e criptografia RSA.  Toda a álgebra necessária é desenvolvida no próprio livro. 

Conteúdo  
  • Primos
  • Grupos abelianos
  • Anéis, ideais e polinômios
  • Testes de primalidade
  • O algoritmo AKS
  • Epílogo
  • Apêndice
  • Bibliografia