The security of cryptosystems like ElGamal and the Elliptic Curve
cryptosystem depends on the complexity of the Discrete Logarithm (DL)
problem in ( G, 
) which is defined as follows.
Given the group (G, 
), 
G,
and 
H, where H is the subgroup generated
by 
, find the unique integer a such that 0 
a
H 
- 1 and 
,
[6] where 
means
The integer a is denoted by 
.
It would seem obvious that at efficient algorithm for discrete logarithms would make several authentication and key exchange systems vulnerable. [3] Thus in view of the difficulty of the DL problem, several authors have proposed algorithms for computing discrete logarithms.
We now restrict ourselves to the discrete logarithms over 
,
p being a prime. The algorithm described by Shank, known as the
``Baby Step - Giant Step'' algorithm, solves the problem in
O(
)steps. In 1978 Stephen Pohlig and
Martin Hellman proposed a new algorithm that performs better for primes p
for which p-1 can be factored into small prime factors.[4]
It is the purpose of this project to realize a full scale implementation of the Pohlig-Hellman algorithm to solve the discrete logarithm problem for primes p of at most 500 digits. Note that the strengh of the Pohlig-Hellman algorithm resides on the fact that p-1 has only small prime factors, thus dividing the original problem into smaller problems that can be solved using Shank's algorithm.
Measurements of the run time of the algorithm were realized for different primes p in which p-1 factors into a product of small primes and an analysis of the complexity of the key subroutines of the program was realized.