Pohlig Hellman Algorithm

The Pohlig-Hellman algorithm can be used when the factorization of the group order q is known. When q has small factors, this technique reduces the given discrete logarithm instance to multiple instances of the discrete logarithm problem in groups of smaller order. Solutions to each of the latter can be combined to give the desired solution to the original problem.

The algorithm was discovered by Roland Silver, but first published by Stephen Pohlig and Martin Hellman (independent of Silver).

Social tagging: