0860

Título
APLICAÇÕES DO TEOREMA DE FERMAT AOS TESTES DETERMINÍSTICOS DE PRIMALIDADE

Aluno: Jean Carlo Baena Vicente - PET - Curso de Matemática (Bacharelado e Licenciatura) (T) - Orientador: Carlos Henrique dos Santos - Departamento de Matemática - Área de conhecimento: 10101039 - Palavras-chave: teste de primalidade; algoritmo aks; números primos.

Atualmente existe uma grande variedade de testes determinísticos de primalidade. Sua função, como o nome já diz, é garantir se um determinado número é primo ou composto. Estes testes são classificados de acordo com o seu tempo de execução em função do valor de entrada do algoritmo.Os testes mais lentos são os de tempo fatorial, eles são fundamentados pelo teorema de Wilson. Algoritmos deste tipo geralmente não são utilizados em computadores, pois no processo serão necessários cálculos de fatoriais, logo, se o número o qual se deseja determinar a primalidade é suficientemente grande, os resultados destes cálculos se tornam demasiadamente extensos para que o computador possa processar.Testes em tempo exponencial, são frutos do resultado obtido por Édouard Lucas em 1856. Infelizmente estes testes também não são utilizados por computadores, salvo alguns casos particulares, o motivo é que para aplicá-lo em um determinado número p se faz necessário que saiba-se como fatorar p-1. Como atualmente não há um algoritmo que faça, de forma simples, a fatoração de um número qualquer, os custos de aplicação deste algoritmo acabam se tornando altos, computacionalmente falando. Apesar disto este algoritmo se mostra muito eficiente ao determinar primalidade de números como os de Mersenne.Em 2002, Manindra Agrawal, Neeraj Kayal e Nitin Saxena publicaram um artigo no qual exibiram o denominado algoritmo AKS", um teste determinístico de primalidade em tempo polinomial. Este foi um feito bem impactante, principalmente porque os conhecimentos exigidos para implementação do algoritmo são relativamente simples, conceitos ensinados a um aluno de graduação.O objetivo deste trabalho é abordar os resultados da teoria algébrica dos números que garantem o funcionamento do algoritmo AKS, apresentando os conceitos e teoremas envolvidos, bem como destacando o papel que desempenha, nesse contexto, os diferentes re-enunciados do Pequeno Teorema de Fermat em associação com o teorema da reciprocidade quadrática, por exemplo.