Baby Steps, Giant Steps
May 6, 2016
In a previous exercise we discussed the discrete logarithm problem, which is to compute the exponent y in the expression xy ≡ n (mod m), given x, n, and m; the modulus m is usually taken as prime. Today we look at an algorithm, known as baby steps, giant steps, that was developed by Daniel Shanks in 1971:
1. Compute limits:
b = ⌈ √m ⌉
h = (x−1)b
2. Construct lists:
A = { xi : i = 0, 1, …, b − 1 } // giant steps
B = { n hj : j = 0, 1, …, b − 1 } // baby steps
3. Sort and find intersection:
Sort the lists A and B
Find an intersection, say xi = n hj
Return y = i + j b
Since m is prime, there must be some y ∈ [0, m) for which xy ≡ n (mod m). Write y = i + j b, where b = ⌈ √m ⌉. Since y must exist, so too i (which counts the giant steps) and j (which counts the baby steps) must exist, and there must be an intersection between the baby steps and the giant steps.
Time complexity is obviously O(sqrt m), which beats the O(m) time complexity of the brute-force algorithm of the previous exercise. There are better algorithms for computing discrete logarithms, which we will study in future exercises.
Your task is to write a program that calculates discrete logarithms using the baby steps, giant steps algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Nice algorithm. Here’s a Python version: essentially we are precomputing values of g^n at intervals of s in the range [0..p-1): this can be done independently of the value whose logarithm we are after (so that can be done in another function that scans backwards from the desired value until it hits a precomputed value). The precise size of the interval s isn’t important for correctness – if s = 1, then we are precomputing everything, if s = p-1 we are precomputing nothing and our algorithm is just a linear scan as before. With s approximately equal to the square root of p, execution time is optimal for calculating a single logarithm. dlog might fail if g isn’t a primitive root (ie. a generator of the group):
import sys import math def egcd (a,b): x,y,z,w = 1,0,0,1 while b != 0: q,r = divmod(a,b) a,b = b,r x,y,z,w = z,w,x-q*z,y-q*w return a,x,y def dlog(g,p): (a,x,y) = egcd(g,p) s = int(math.sqrt(p)) h = pow(g,s,p) big = {} i = 0; while i*s < p-1: big[pow(h,i,p)] = i i += 1 def aux(n): for i in range(s): if n in big: return s*big[n]+i n = n*x%p return aux g,p = int(sys.argv[1]),int(sys.argv[2]) f = dlog(g,p) print [f(i) for i in range(1,p)] # $ dlog.py 7 23 # [0, 14, 2, 6, 7, 16, 1, 20, 4, 21, 19, 8, 10, 15, 9, 12, 5, 18, 17, 13, 3, 11][…] studied discrete logarithms in two previous exercises. Today we look at a third algorithm for computing discrete algorithms, invented by John Pollard in […]