It was found by [4] that the Pohlig-Hellman algorithm is most
efficient when p-1 has only small prime factors. In contrast, the
algorithm is least efficient when 
where p'is also a
prime and of the same order as p . For 200 digit long primes the requirements of
memory are too large and thus, it is infeasible to apply the Pohlig-Hellman Algorithm to solve the
discrete logarithm problem in these fields.
Another fact is important to point out. Accordding to [3]
the complexity of the algorithm is O(
) group operations using O(
) bits of memory and
provided that a precomputation requiring O(
)
field operations is carried out first. This project will be compared to the results in [3],
each part of the program will be analyzed independently, and then combined
for an overall estimate of the complexity of the implementation. Finally, tests of the run time of the program
were realized and tabulated in section 4.3 (All the tests presented in this section were performed on a 175 MHz
Alpha processor with 128 Mb of RAM, unless otherwise stated).