Shank’s Babystep - Gianstep Algorithm

Math 302 Cryptography, February 13, 2017
T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Defining the procedure to solve (g^x) = h  mod p

This is not the most efficient or elegant implementation, but it is pretty succinct!

shanks[g_,h_,p_]:= Module[ {n, list1,list2,match,i,j,x},
n=Floor[Sqrt[MultiplicativeOrder[g,p]]]+1;

list1 = Table[ Mod[g^i,p],{i,0,n}];
list2 = Table[Mod[h*PowerMod[g,-n*j,p],p],{j,0,n}];
match=Intersection[list1,list2][[1]];

i=Flatten[Position[list1,match]][[1]]-1;
j=Flatten[Position[list2,match]][[1]]-1;
x=n*j+i;

Print["len(list1) = ",Length[list1],"\nlen(list2) = ",Length[list2],"\n"];
Print["x = ",x, " is a solution to \n\n     ",g,"\!\(\*SuperscriptBox[\(\), \(x\)]\) = ",h," mod ",p];

Return[ ]
]

Now let’s call the procedure to solve (2^x)= 7 mod 29

shanks[2,7,29]

Let’s try it on some larger values

p=Prime[10000];
g=PrimitiveRoot[p];
h=RandomInteger[{2,p-1}];

shanks[g,h,p]