(Sócio):10.80       (Não Sócio):12.00      
Adicionar ao carrinho

Primalidade em Tempo Polinomial - Uma introdução ao Algoritmo AKS


Apesar do estudo de métodos para determinar se um número é primo ter ocupado matemáticos como Euler e Fermat, esta área saiu de moda no século XIX, e a situação só mudaria nos anos de 1970, com o desenvolvimento dos métodos de criptografia de chave pública. O estudo da complexidade de algoritmos, iniciado por volta da mesma época, levaria os matemáticos a formular o objectivo da sua busca nesta área como o de obter um algoritmo determinístico de primalidade, com custo polinomial. Mesmo com os avanços significativos alcançados nos trinta anos seguintes, o século XX encerrou com os testes de primalidade divididos em duas classes. De um lado algoritmos que, embora rápidos, estão sujeitos a uma certa margem de erro, de outro algoritmo cujos resultados são garantidos, mas com um desempenho que deixa muito a desejar. Ainda era este o estado das coisas quando o Algoritmo AKS foi publicado na internet em Agosto de 2002. Criado pelos indianos Agrawa, Kayal e Saxena, o algoritmo é, ao mesmo tempo, eficiente e deterministico. Isso é, além de sempre retornar correctamente se o numero testado é primo ou composto, o algoritmo faz isso num tempo que é proporcional.
Categorias:
  • Livros Sociedade Brasileira de Matemática
  • Colecção Iniciação Cientifica

  • Autor: S. C. Coutinho