The Pohlig-Hellman algorithm, sometimes credited as the Silver-Pohlig-Hellman algorithm, is a special-purpose algorithm for computing discrete logarithms in a finite abelian group whose order is a smooth integer. It was introduced by Roland Silver but first published by Stephen Pohlig and Martin Hellman, who credited Silver with its earlier independent but unpublished discovery; Pohlig and Hellman also noted that Richard Schroeppel and H. Block had found the same algorithm later than Silver, also without publishing it.
Connections
Associated With
Fellow discrete-logarithm algorithms directly compared in the literature. Verified en.wikipedia.org/wiki/Pohlig-Hellman_algorithm, which uses baby-step giant-step as a named subroutine ("Using the baby-step giant-step algorithm, compute...") and states Pohlig-Hellman is more efficient than baby-step giant-step alone when the group order is composite.
Invented By
Co-published with Stephen Pohlig; the algorithm bears both names. Verified en.wikipedia.org/wiki/Pohlig-Hellman_algorithm: "The algorithm was introduced by Roland Silver, but first published by Stephen Pohlig and Martin Hellman, who credit Silver with its earlier independent but unpublished discovery." Not overclaimed as sole or first discovery given Silver's earlier unpublished work.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.