An Interactive Applet powered by Sage and MathJax.
(By Alyssa Vorpahl and Prof. Gregory V. Bard)
Previously (here), we saw a brute-force method for solving the discrete logarithm problem. Here, we will see a vastly more efficient way to solve it, called the "Baby-Step/Giant-Step Algorithm".
Brute-forcing every possible exponent for the discrete logarithm problem will eventually reach the correct solution, but as the modulus p gets larger, it becomes less feasible to use that approach. As a result, brute-force isn't a threat to modern cryptographic methods. However, there are faster methods that can be used to solve the discrete log problem, one of which is the Baby-Step/Giant-Step algorithm.
To begin the algorithm, we find the square root of p, rounding any decimal up to the next integer, and store that as B. In other words, B = ceiling(sqrt(p)). We then calculate g^i mod p for each i such that 0 ≤ i < B, storing the pair (g^i, i) within a list, called listOne. We also calculate y*g-B*i mod p for each i such that 0 ≤ i < B, storing the pair (y*g-B*i, i) in a list, called listTwo.
Note, each entry in listOne is g times the previous entry in the list mod p, and these are the 'baby steps'. Similarly, each entry in listTwo is g-B times the previous entry in the list mod p, and these are the 'giant steps'. For example, with g=2, p=101, and B=11, each entry in listOne is 2 times the previous entry, and each entry in listTwo is 83 times the previous entry (since 83 = 2-11 mod 101).
We then sort the two lists in ascending order based on gi and y*g-B*i, respectively. Once the lists are sorted, we compare the lists to see if there is a match between the first entry of the ordered pairs. Such a pair would look like (gj, j) and (y*g-B*k, k) for some j and k, with gj = y*g-B*k mod p. If a match is found, we extract the paired j and k for those values.
Such a pair has gj = y*g-B*k, which means gj*gB*k = y. Since ab*ac = ab+c, we have gj+B*k = y. This means that x = j+b*k and gx = y. We return j+B*k as the discrete logarithm (base g) of y in the group G.
Despite being a more complicated process than simply checking each possible x value (brute force), this algorithm is much faster. Brute force has algorithmic complexity of O(p), whereas this algorithm has complexity O(B*log(B)), because the longest step is sorting the two lists. This is equivalent to O(sqrt(p)*log(p)), since B = ceil(sqrt(p)) and log(B) = log(sqrt(p)) = log(p)/2.
To be explicit, for p roughly equal to one trillion, brute force would require one trillion modular exponentiations. The Baby-Step/Giant-Step Algorithm requires B roughly equal to one million, so two million modular exponentiations (one million per list), and forty million comparisons (twenty million per list). Note that while it is faster, it's still not fast enough to threaten modern cryptographic methods.
Once you load the applet, there will be 3 sliders: one to control the desired y value, one to control the modulus for the group G = Zp, and one to control the generator g. Once all of the initial conditions are verified (the modulus must be a prime, g must generate Zp, and y must < p) to ensure that the discrete logarithm problem has a solution.
Once that has been verified, the app will calculate sqrt(p) as B, then calculate listOne and listTwo, as well as sort them. It will then compare the values in each list until it finds a match, then return x = j+k*B such that gx = y mod p