Implementation of the Pohlig-Hellman Algorithm
for the Discrete Logarithm Problem
Jorge Guajardo
Pedro Soria-Rodríguez
December 5, 1995
Abstract:
The security of cryptosystems like ElGamal and the Elliptic Curve
cryptosystem depends on the complexity of the Discrete Logarithm (DL)
problem. Several algorithms have been proposed to solve the DL problem.
Among these, the Pohlig-Hellman algorithm stands out for particular choices
of primes p in fields 
. In this project, a full size implementation
of the Pohlig-Hellman Algorithm was realized and tests were performed to find the run
time of the program for primes of different size. In addition, the complexity of our
implementation was estimated to be O(
)
and it was compared to the complexities of the algorithm according to several authors .
Contents:
Pedro Soria-Rodriguez
,
Sat Mar 16 16:13:36 EST 1996.