Shank’s Babystep-Giantstep Algorithm
Math 302 Advanced Cryptography
February 11, 2019

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

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 where they agree

Intersection[babySteps,giantSteps]

Let’s get the positions in the babyStep and giantStep lists where we agree
Note that the lists start with i=0 and j=0, so we’ll need to subtract 1 from the position

match=
Position[babySteps,match]
Position[giantSteps,match]

Now let’s compute our solution

i=
j=
x=i+j*n

And verify that we have a solution

PowerMod[g,x,p]

Or a more automated, but less readable form

g=2; h=21; p=29;

n=Floor[Sqrt[MultiplicativeOrder[g,p]]]+1;
babySteps = Table[ PowerMod[g,i,p],{i,0,n}];
giantSteps = Table[ Mod[h*PowerMod[g,-n*j,p],p],{j,0,n}];
match=Intersection[babySteps,giantSteps][[1]];
i=Position[babySteps,match][[1,1]]-1;
j=Position[giantSteps,match][[1,1]]-1;
x= n*j+i;

Print[Row[{"\nA solution to ",g,"^x = ",h," mod ",p,"  is   x = ",x}, BaseStyle->{"Subsection"}]];
Print["\ng=",g,", h=",h,", p=",p,", n= ",n];
Print["babySteps: ",babySteps];
Print["giantSteps: ",giantSteps];
Print["First matching value: ",match];
Print["i=",i , ",  j=",j];
Print["Verify by calculating (g^x) mod p = ", PowerMod[g,x,p]];