February 21, 2023
Math 302 Cryptography
Spring 2023

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Shank’s Babystep-Giantstep to solve  (g^x) ≡ h mod p

These are all the commands from last week’s notebook (feb14.nb) combined in one cell.
I added semicolons to suppress the output so it won’t print out the babystep and giantstep lists. 

Just change the values of g, h, and p to solve (g^x) ≡ h mod p

If you want to look at Mathematica’s syntax for Module[ ], it’s not hard to convert this to a function.

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];
collision = match[[1]];
bsPos = Position[babySteps,collision];
gsPos = Position[giantSteps,collision];
i=bsPos[[1,1]] - 1;
j =gsPos[[1,1]] - 1;
x=i+j*n;
Print["x = ",x, "\nIs g^x = h mod p? ", PowerMod[g,x,p]==h]

Some other commands that will be useful

To find the prime factorization of an integer:
Note this will choke on RSA sized integers, otherwise RSA wouldn’t be secure!

FactorInteger[16665249400]

To solve the system 
	x ≡ 6 mod 7,    x ≡ 4 mod 8,   x ≡  10 mod 15
using the Chinese Remainder Theorem:

ChineseRemainder[{6,4,10},{7,8,15}]

To find the number of digits in the binary representation of a number: 
You can also change the base from 2 to other values.

IntegerLength[4234253253,2]

The values for #2 from the Tutorial

p=129003898576076751531908549775811
g=10
h=50613106319218605201866538939818