Baby-step giant-step

The algorithm

Input: A cyclic group G of order n, having a generator α and an element β.

Output: A value x satisfying ${\displaystyle {\alpha }^x=\beta }$.

1. m ← Ceiling(√n)
2. For all j where 0 ≤ j < m:
   1. Compute α^j and store the pair (j, α^j) in a table. (See § In practice)
3. Compute α^−m.
4. γ ← β. (set γ = β)
5. For all i where 0 ≤ i < m:
   1. Check to see if γ is the second component (α^j) of any pair in the table.
   2. If so, return im + j.
   3. If not, γ ← γ • α^−m.

In practice

The best way to speed up the baby-step giant-step algorithm is to use an efficient table lookup scheme. The best in this case is a hash table. The hashing is done on the second component, and to perform the check in step 1 of the main loop, γ is hashed and the resulting memory address checked. Since hash tables can retrieve and add elements in ${\displaystyle O(1)}$ time (constant time), this does not slow down the overall baby-step giant-step algorithm.

The space complexity of the algorithm is ${\displaystyle O(\sqrt{n})}$, while the time complexity of the algorithm is ${\displaystyle O(\sqrt{n})}$. This running time is better than the ${\displaystyle O(n)}$ running time of the naive brute force calculation.

The baby-step giant-step algorithm could be used by an eavesdropper to derive the private key generated in the Diffie Hellman key exchange, when the modulus is a prime number that is not too large. If the modulus is not prime, the Pohlig–Hellman algorithm has a smaller algorithmic complexity, and potentially solves the same problem.