## 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),int(sys.argv)
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 […]