Baby-step giant-step

The algorithm is based on a space–time tradeoff. It is a fairly simple modification of trial multiplication, the naive method of finding discrete logarithms.

Given a cyclic group ${\displaystyle G}$  of order ${\displaystyle n}$ , a generator ${\displaystyle \alpha }$  of the group and a group element ${\displaystyle \beta }$ , the problem is to find an integer ${\displaystyle x}$  such that

${\displaystyle \alpha ^{x}=\beta \,.}$ 

The baby-step giant-step algorithm is based on rewriting ${\displaystyle x}$ :

${\displaystyle x=im+j}$ 

${\displaystyle m=\left\lceil {\sqrt {n}}\right\rceil }$ 

${\displaystyle 0\leq i<m}$ 

${\displaystyle 0\leq j<m}$ 

Therefore, we have:

${\displaystyle \alpha ^{x}=\beta \,}$ 

${\displaystyle \alpha ^{im+j}=\beta \,}$ 

${\displaystyle \alpha ^{j}=\beta \left(\alpha ^{-m}\right)^{i}\,}$ 

The algorithm precomputes ${\displaystyle \alpha ^{j}}$  for several values of ${\displaystyle j}$ . Then it fixes an ${\displaystyle m}$  and tries values of ${\displaystyle i}$  in the right-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 ${\displaystyle j}$ , using the precomputed values of ${\displaystyle \alpha ^{j}}$ .

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.

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.^[2]

• The baby-step giant-step algorithm is a generic algorithm. It works for every finite cyclic group.
• It is not necessary to know the exact order of the group G in advance. The algorithm still works if n is merely an upper bound on the group order.
• Usually the baby-step giant-step algorithm is used for groups whose order is prime. If the order of the group is composite then the Pohlig–Hellman algorithm is more efficient.
• The algorithm requires O(m) memory. It is possible to use less memory by choosing a smaller m in the first step of the algorithm. Doing so increases the running time, which then is O(n/m). 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.
• While this algorithm is credited to Daniel Shanks, who published the 1971 paper in which it first appears, a 1994 paper by Nechaev^[3] states that it was known to Gelfond in 1962.
• There exist optimized versions of the original algorithm, such as using the collision-free truncated lookup tables of ^[4] or negation maps and Montgomery's simultaneous modular inversion as proposed in.^[5]

• H. Cohen, A course in computational algebraic number theory, Springer, 1996.
• D. Shanks, Class number, a theory of factorization and genera. In Proc. Symp. Pure Math. 20, pages 415—440. AMS, Providence, R.I., 1971.
• A. Stein and E. Teske, Optimized baby step-giant step methods, Journal of the Ramanujan Mathematical Society 20 (2005), no. 1, 1–32.
• A. V. Sutherland, Order computations in generic groups, PhD thesis, M.I.T., 2007.
• D. C. Terr, A modification of Shanks’ baby-step giant-step algorithm, Mathematics of Computation 69 (2000), 767–773. doi:10.1090/S0025-5718-99-01141-2

• Baby step-Giant step – example C source code