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.

Pages: 1 2

2 Responses to “Baby Steps, Giant Steps”

  1. matthew said

    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]
    
  2. […] studied discrete logarithms in two previous exercises. Today we look at a third algorithm for computing discrete algorithms, invented by John Pollard in […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: