Algorithm for solving the discrete logarithm problem
In group theory, a branch of mathematics, the baby-step giant-step is a meet-in-the-middle algorithm for computing the discrete logarithm or order of an element in a finite abelian group by Daniel Shanks. 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; the more difficult it is, the more security it provides a data transfer. One way to increase the difficulty of the discrete log problem is to base the cryptosystem on a larger group.
Theory.
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 formula_1 of order formula_2, a generator formula_3 of the group and a group element formula_4, the problem is to find an integer formula_5 such that
 formula_6
The baby-step giant-step algorithm is based on rewriting formula_5:
formula_8
formula_9
formula_10
formula_11
Therefore, we have:
 formula_12
 formula_13
 formula_14
The algorithm precomputes formula_15 for several values of formula_16. Then it fixes an formula_17 and tries values of formula_18 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 formula_16, using the precomputed values of formula_15.
The algorithm.
Input: A cyclic group "G" of order "n", having a generator "α" and an element "β".
Output: A value "x" satisfying formula_21.
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 formula_22 time (constant time), this does not slow down the overall baby-step giant-step algorithm.
The space complexity of the algorithm is formula_23, while the time complexity of the algorithm is formula_24. This running time is better than the formula_25 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.
References.
 ;templatestyles src="Reflist/styles.css" / ;