Pollard’s ρ 
Math 302 Cryptography
February 3, 2025

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Useful commands for in-class work, #1

This sequence of commands will build the first n terms of the sequence {(Subscript[x, i])} where  
(Subscript[x, 0])=1  and (Subscript[x, i+1])=f((Subscript[x, i])) with f(x)=5x mod 85
and then print    i  (Subscript[x, i])

n=40;
x0 = 1;
f[x_]:= Mod[5x, 85];
xList = {x0};
For[i=1,i<n,i++,
AppendTo[xList, f[ Last[xList]]]
]
Transpose[ {Table[i, {i,0,n-1}],xList}] //TableForm

Useful functions for in-class work, #2

This defines the function pollardsRho[g,h,p]   and the auxiliary functions  f[ ], nextAlpha[ ], and nextBeta[ ]
You only need to call pollardsRho[g, h, p] to find the collision.

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_]:= Module[{x=1,α=0,β=0,y=1,γ=0,δ=0,i,u,v},

For[i=1,(i==1)||(x≠y),i++,

α=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["\nCOLLISION AT\ni = ",i-1,":    (Subscript[x, i]) = ",x,", (Subscript[α, i]) = ",   α,", (Subscript[β, i]) = ",β,":     (Subscript[y, i]) = ",y,", (Subscript[γ, i]) = ",γ,", (Subscript[δ, i]) = ",δ] ;
];

Find the collision for the DLP (11^x) ≡ 37 mod 71
Note that you still need to do some more work to find x!

pollardsRho[11, 37, 71]