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