11 a 14 de dezembro de 2012 – Campus de Palmas
Algoritmo AKS
Rodrigo Reis Pereira
Nome do Aluno: Rodrigo Reis Pereira; Nome do Orientador: Fernando Soares de Carvalho
aluno do Curso de Matemática; Campus de Arraias; e-mail: [email protected]
Orientador(a) do Curso de Matemática; Campus de Arraias; e-mail: [email protected]
RESUMO
A base da importância do estudo do algoritmo AKS é a criptografia de chave pública
que é um método de encriptação muito utilizado hoje em dia, e estudos foram feitos
para o aperfeiçoamento da segurança desse sistema. Entretanto, essa ciência precisa ser
constantemente aprimorada devido ao avanço da velocidade dos computadores, os quais
estão se tornando cada vez mais capazes de fazer uma criptoanálise eficiente em um
tempo relativamente curto. Um fator importante para garantir a segurança de uma
criptografia é o tamanho das chaves, que são números primos. Atualmente dispõe-se de
algoritmos probabilísticos que acusam se um número é primo com baixíssimo
percentual de erro, em tempo polinomial. O AKS é o primeiro algoritmo determinístico
a executar este teste em tempo polinomial. O objetivo deste trabalho é entender
Conhecer sobre a teoria matemática envolvida no Algoritmo AKS. Fornecer uma
descrição completa e detalhada do conteúdo envolvido ao Algoritmo AKS. Mostrar os
testes básicos utilizados para identificar um número composto.
.
Palavras – chave: Algoritmo AKS; criptografia RSA; número - primo.
INTRODUÇÃO
11 a 14 de dezembro de 2012 – Campus de Palmas
O problema que será estudado é um teste de primalidade de um número inteiro, ou seja,
decidir se um inteiro é primo ou composto. O conceito de número primo foi introduzido
na Grécia Antiga, vamos encontrá-lo, por exemplo, nos Elementos de Euclides, escrito
por volta de 300 a.C.. Segundo a definição, um número inteiro p > 1 é primo se no
conjunto de seus divisores figurarem somente dois números distintos: 1 e p. Se o
conjunto possuir tamanho maior que 2, o número é dito composto.
Existem dois tipos de algoritmos envolvendo primos: os crivos (como por exemplo, o
Crivo de Eratóstenes) que enumeram primos dentro de um intervalo e os algoritmos
que, dado um número maior que 1, verificam se ele é primo. Este trabalho tem foco em
um algoritmo que pertence ao segundo conjunto: o Algoritmo AKS, que foi divulgado
na web, em agosto de 2002, pelos indianos Agrawal, Kayal e Saxena).
A aplicação mais conhecida para os números primos é a criptografia de chave pública,
que permite transações bancárias seguras e encriptação de emails ou de dados num
disco rígido. Tudo para que terceiros não tenham acesso a informações que devem ser
protegidas. Um dos algoritmos mais conhecidos é o RSA, que envolve a multiplicação
de dois números primos p e q.
.
Materiais e Métodos
- Revisão de bibliográfica e levantamento de novas fontes bibliográficas a serem
utilizadas.
- Análise de problemas propostos relacionados ao objeto de estudo.
- Estudo individual e reuniões com o orientador.
11 a 14 de dezembro de 2012 – Campus de Palmas
RESULTADOS E DISCUSSÃO
Fizemos um estudo detalhado do conteúdo matemático envolvido no algoritmo AKS,
com conseqüência produzimos um material de linguagem simples e detalhada de tudo
estudado, mostrando a importância da álgebra para o funcionamento do algoritmo AKS.
LITERATURA CITADA
- Agrawal, M., N. Kayal e N. Saxena. 2002 Primes is im P, IIT, preprint, disponível em
http//www.cse.utk.ac.in/news/primality.pdf
- Coutinho,S.C.. Números Inteiros e Criptigrafia RSA. 2001 – Série Computação e
Matemática, IMPA, Rio de Janeiro.
- Coutinho,S.C.. Primalidade em tempo Polinomial: Uma Introdução ao Algoritmo
AKS. 2004 – Coleção Iniciação Científica, IMPA, Rio de Janeiro.
- Landau, E.. Teoria Elementar dos Números. 2002 – Coleção Clássicos da Matemática,
Editora Ciência Moderna, Rio de Janeiro.
- Voloch, J. F.. A Distribuição dos Números Primos. 1987 – Matemática Universitária,
número 06, 71-82.
AGRADECIMENTOS
Agradeço a Deus por ter me dado saúde e capacidade para executar esse trabalho, ao
meu orientador por ter me convidado para trabalhar esse projeto. A UFT.
O presente trabalho foi realizado com o apoio da UFT.