Baby Steps, Giant Steps

May 6, 2016

The algorithm given on the prior page does more work than is strictly necessary. Instead of computing both A and B, we will store the elements of A in a hash table as they are computed, then check each element of B as it is computed, and if it is in A, immediately compute the discrete logarithm. Also, instead of computing the various powers, we accumulate them by multiplication in the two do loops

(define (baby-step-giant-step x n m)
  (let* ((b (inexact->exact (ceiling (sqrt m))))
         (h (expm (inverse x m) b m))
         (a (make-eq-hashtable)))
    (do ((i 0 (+ i 1)) ; giant steps
         (xi 1 (modulo (* xi x) m)))
        ((= i b))
      (hashtable-set! a xi i))
    (do ((j 0 (+ j 1)) ; baby steps
         (nhj n (modulo (* nhj h) m)))
        ((hashtable-ref a nhj #f)
          (+ (hashtable-ref a nhj #f) (* j b))))))

The first do-loop takes time O(sqrt m), and the second do-loop takes on average O(1/2 sqrt m), for a total time complexity of O(sqrt m); both inner loops consist of an addition, a modular multiplication, a hashtable operation, and a termination test. Here is an example, and a check that shows the answer is correct:

> (baby-step-giant-step 3 13 17)
4
> (expm 3 4 17)
13

Thus, 34 ≡ 13 (mod 17). You can run the program at http://ideone.com/aft1PN, where you will also see expm from the Standard Prelude and a function that computes the modular inverse by Fermat’s Little Theorem.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: