## 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 xyn (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 xyn (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.