The baby-step giant-step algorithm is a meet-in-the-middle algorithm, devised by Daniel Shanks, for computing the discrete logarithm or the order of an element in a finite abelian group, a problem of fundamental importance to public-key cryptography. Many widely used cryptographic systems rest on the assumption that the discrete logarithm problem is extremely difficult to solve, so the security such systems provide can be increased by basing them on a larger group.
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.
Verified en.wikipedia.org/wiki/Baby-step_giant-step: "Alternatively one can use Pollard's rho algorithm for logarithms, which has about the same running time as the baby-step giant-step algorithm, but only a small memory requirement."
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.