Pohlig–Hellman algorithm for computing discrete logarithms
- by drelihan
Hi Folks,
I'm working on coding the Pohlig-Hellman Algorithm but I am having problem understand the steps in the algorithm based on the definition of the algorithm.
Going by the Wiki of the algorithm: http://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm
I know the first part 1) is to calculate the prime factor of p-1 - which is fine.
Howeever, I am not sure what I need to do in steps 2) and 3).
Can someone help with explaining this in plain english (i) - or pseudocode. I want to code the solution myself obviously but I cannot make any more progress unless i understand the algorithm.
Note: I have done a lot of searching for this and I read S. Pohlig and M. Hellman (1978). "An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance but its still not really making sense to me.
Thanks in advance