Transcript
Resumo Este trabalho tem por objetivo discutir um problema que intriga os matemáticos desde os tempos antigos: a Primalidade de números. Analisamos a evolução dos testes de primalidade ao longo do tempo: desde o mais antigo conhecido, o Crivo de Erathostenes, testes mais atuais e probabilísticos, como o de Monte Carlo, até o algoritmo que causou grande impacto na comunidade matemática: o AKS, que não só determina se um número é primo, como faz isso em tempo polinomial. Para desenvolvermos nosso trabalho, nós apresentamos estudos básicos sobre estruturas algébricas, teoria dos números e teoria dos algoritmos. Damos uma descrição histórica de alguns testes e analisamos, particularmente, o algoritmo AKS. Abordamos também a área de Criptografia como uma aplicação dos números primos em nossos dias. Por fim, como apêndice a este trabalho, damos um exemplo de implementação do algoritmo AKS. Abstract In this work we study the primality tests and its evolution along the time, since the Erathostenes Crive until the actual probabilistic and deterministic tests like Monte Carlo’s and the algorithm which caused great impact in the mathematical community: the AKS Test. To develop our work, we treat basic concepts about algebraic structures, number theory and theory of algorithms. We give a historical description of some tests and analyze, particularly, the AKS algorithm. We also analyze the costs of algorithms in order to verify if a test takes a polynomial or exponential time. The area of Cryptography is viewed in our work as an application of the prime numbers in our days. Finally, we give an implementation example of the AKS algorithm.
