O problema do logaritmo discreto

Abstract

Existem muitos sistemas de criptografia cuja segurança é baseada na dificuldade em resolver logaritmos discretos. Neste trabalho descrevemos alguns métodos para calcular logaritmos discretos, a saber: Algoritmo Shanks, Algoritmo Pollard, Algoritmo Silver-Pohlig-Hellman e o Algoritmo Index Calculus. Também são relatadas questões de complexidade computacional e os últimos recordes alcançados para resolver logaritmos discretos.

There are many cryptosystems whose security is based on the difficulty of solving the discrete logarithm. In this work, we describe some methods to calculate discrete logarithms: Shanks's Algorithm, Pollard's Algorithm, Silver-PohligHellman's Algorithm and the Index Calculus Algorithm. We also relate computation complexity issues and the last records that have been obtained on the discrete logarithm problem.