Pollard’s ρ Method for the DLP in (Subscript[𝔽, p])
Math 302 Advanced Cryptography
February 25, 2019

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Defining the functions

These functions implement Pollard’s ρ Method as described in the text (Hoffstein, Pipher, and Silverman, 2nd Edition, Section 5.5.2) to solve the DLP (g^x)≡ h mod p

You call the function by
	pollardsRho[g, h, p, printFreq]
where printFreq indicates that the function should print out the results of the ith stage if i ≡ 0 mod printFreq 

This function call will only give you the information for the collision. You will still need to take a vth root mod p in order to solve the given DLP.

f[x_,g_,h_,p_]:=  Mod[Piecewise[
{{g*x, 0 ≤ x < p/3},
{x^2, p/3 ≤ x < 2p/3},
{h*x, 2p/3 ≤ x < p}}] , p]

nextAlpha[ai_,xi_,p_]:= Mod[Piecewise[
{{ai+1, 0 ≤ xi < p/3},
{2ai, p/3 ≤ xi < 2p/3},
{ai, 2p/3 ≤ xi < p}}] , p-1]

nextBeta[bi_,xi_,p_]:= Mod[Piecewise[
{{bi, 0 ≤ xi < p/3},
{2bi, p/3 ≤ xi < 2p/3},
{bi+1, 2p/3 ≤ xi < p}}] , p-1]

pollardsRho[g_,h_,p_,printFreq_]:= Module[{x=1,α=0,β=0,y=1,γ=0,δ=0,i},

For[i=1,(i==1)||(x≠y),i++,
If[ Mod[i,printFreq]==0, 
Print["i = ",i-1,":    x = ",x,", α = ",   α,", β = ",β,":     y = ",y,", γ = ",γ,", δ = ",δ] 
];

α=nextAlpha[α,x,p];
β=nextBeta[β,x,p];
x=f[x,g,h,p];

γ=nextAlpha[γ,y,p];
δ=nextBeta[δ,y,p];
y=f[y,g,h,p];

γ=nextAlpha[γ,y,p];
δ=nextBeta[δ,y,p];
y=f[y,g,h,p]
];

Print["\n\nCOLLISION AT\ni = ",i-1,":    x = ",x,", α = ",   α,", β = ",β,":     y = ",y,", γ = ",γ,", δ = ",δ] ;

]

Applying to Exercise 2.17(a) and print every iteration

pollardsRho[11,21,71,1]

Looking at a larger example

p=Prime[10000000000]
g=PrimitiveRoot[p]
h=RandomInteger[{1,p-1}]
Print["Shanks would create lists of length Sqrt[ord[g]] = ",Floor[Sqrt[(p-1)]]]

pollardsRho[g,h,p,100000]