Algoritmo AKS Primalidade de um Número em Tempo Polinomial

 Os  algoritmos  para  determinação  de  primalidade  são  importantes  na  obtenção  de  números  primos  muito grandes,  usados  na  confecção  de  chaves  privadas  de  encriptação.  Atualmente  dispõe-se  de  algoritmos probabilísticos que executam em tempo polinomial e acusam se um número é primo com baixíssimo percentual de erro. O AKS é o primeiro algoritmo determinístico a executar este teste em tempo polinomial. Neste artigo, discutimos as bases matemáticas deste algoritmo e apresentamos uma implementação na linguagem do Maple.