Pohlig-Hellman Algorithm 
Math 302 Advanced Cryptography
February 20, 2019

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Solve (2^x) ≡ 1 048 569 mod 2 038 074 803

p=2038074803;g=2;h=1048569; 
bigN=MultiplicativeOrder[g,p]

FactorInteger[bigN]

Define the g’s and h’s for the smaller DLPs

g1=PowerMod[g,bigN/2,p];
g2=PowerMod[g,bigN/103,p];
g3=PowerMod[g,bigN/659,p];
g4=PowerMod[g,bigN/15013,p];
h1=PowerMod[h,bigN/2,p];
h2=PowerMod[h,bigN/103,p];
h3=PowerMod[h,bigN/659,p];
h4=PowerMod[h,bigN/15013,p];

Let’s look at the values

{g1,g2,g3,g4}
{h1,h2,h3,h4}

We can define a function to apply Shanks to each of the smaller DLPs

shanks[g_,h_,p_]:=Module[{n,babySteps,giantSteps,match,i,j,x},
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;
Return[x]
]

shanks[g1,h1,p]
shanks[g2,h2,p]
shanks[g3,h3,p]
shanks[g4,h4,p]

Now let’s apply the Chinese Remainder Theorem to get our solution to the original DLP

ChineseRemainder[{1,47,139,4829},{2,103,659,15013}]

And verify that this answer is correct!

PowerMod[g, 2022766371,p]

This is why we want g to have large prime order! 
If N=ord(g) factors, then we can apply Pohlig-Hellman to solve smaller DLPs.

Why doesn’t this work all the time? 

Let’s look at the 1536-bit group from  https://tools.ietf.org/html/rfc3526

p = 2^1536-2^1472-1+2^64*(Floor[2^1406 *Pi]+741804)

PrimeQ[p]

q=MultiplicativeOrder[2,p]

PrimeQ[q]

n=Floor[Sqrt[q]]+1

Length[IntegerDigits[n]]

Since N=ord(q) is prime, we can’t break this down into smaller DLPs to solve. 

If we apply Shanks directly, we would need to build two lists that have (10^232)elements. 

Bummer. Our lists are longer than the number of atoms in the observable universe