Shank’s Babystep-Giantstep for the DLP 
Math 202 Cryptography
November 11, 2024

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Shank’s Babystep-Giantstep to solve  (2^x) ≡ 21 mod 29

Define g, h, p, and n so that we can reuse this code for other examples

g=2; h=21; p=29;
n=Floor[Sqrt[MultiplicativeOrder[g,p]]]+1

Let’s build the lists

babySteps = Table[ PowerMod[g,i,p],{i,0,n}]
giantSteps = Table[ Mod[h*PowerMod[g,-n*j,p],p],{j,0,n}]

Now look for values that the lists have in common (the collisions)

match = Intersection[babySteps,giantSteps]

Since match is a list, let’s take the first element of match as our collision 

Let’s get the positions in the babyStep and giantStep lists of the collision

collision = match[[1]]
bsPos = Position[babySteps,collision]
gsPos = Position[giantSteps,collision]

Mathematica’s Position[ ] function returns the result as a list of lists, so we can extract this value with the [[1,1]] index

Since our lists start with i=0 and j=0, so we’ll need to subtract 1 from the position

i=bsPos[[1,1]] - 1
j =gsPos[[1,1]] - 1

Now we can compute our solution x = i + j*n
And be sure to verify your answer: (g^x) ≡ h mod p