In group theory, a branch of mathematics, the baby-step giant-step algorithm refers to a series of well defined steps to compute the discrete logarithm. The discrete log problem is of fundamental importance to the area of public key cryptography. Many of the most commonly used cryptography systems are based on the assumption that the discrete log is extremely difficult to compute. Clearly, the more difficult it is, the more secure it is to transfer data over the internet or any other medium susceptible to interceptions of signals. One way to increase the difficulty of the discrete log problem is to base the crypto-system on a larger group.

The generalised form of baby-step giant-step algorithm can be implemented to compute the discrete log of any abelian group.

Theory

---

The algorithm is based on a space-time tradeoff. It is a fairly simple modification of trial multiplication, the naïve method of finding discrete logarithms.

The problem is to find x where

$\backslash alpha^x\backslash equiv\backslash beta\backslash pmod\{n\}$

where α, β and n are given. The baby-step giant-step algorithm is based on rewriting x as x = im + j, with m constant and 0 ≤ i, j < m. Therefore, we have:

$\backslash beta(\backslash alpha^\{-m\})^i\backslash equiv\backslash alpha^j\backslash pmod\{n\}.$

The algorithm precomputes α^j for several values of j. Then it fixes an m and tries values of i in the left-hand side of the congruence above, in the manner of trial multiplication. It tests to see if the congruence is satisfied for any value of j, using the precomputed values of α^j.

The algorithm

---

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

Output: A value x satisfying $\backslash alpha^\{x\}\backslash equiv\backslash beta\backslash pmod\{n\}$.

1. m ← Ceiling(√n)
2. For all j where 0 ≤ j < m:
   1. Compute α^j mod n and store the pair (j, α^j) in a table. (See section "In practice")
3. Compute α^−m.
4. γ ← β.
5. For i = 0 to (m − 1):
   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 mod n.

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 O(1) time (constant time), this does not slow down the overall baby-step giant-step algorithm.

The running time of the algorithm is:

$O(\backslash sqrt\{n\}).$

The space complexity is the same.

Reference

---

D. Shanks. Class number, a theory of factorization and genera. In Proc. Symp. Pure Math. 20, pages 415--440. AMS, Providence, R.I., 1971.

group theory

Babystep-Giantstep-Algorithmus