Pollard rho solves a generic discrete logarithm by turning the group into a pseudorandom walk and waiting for the birthday paradox to produce a collision.
The method needs very little memory. Every visited group element is tracked together with coefficients a,b satisfying X=g^a h^b. When the same X is reached by two different coefficient pairs, the equality becomes a linear congruence in the unknown logarithm x.
This is Guide 26 in the Bukit Timah Tutor Computational Number Theory series. It deepens the overview in Guide 6 and complements Guide 25: Pohlig–Hellman.
1. The generic discrete-log problem
Let G=<g> have order N, and suppose
h=g^x.
We want x modulo N.
Baby-step giant-step reaches square-root time with square-root memory. Pollard rho aims for the same generic square-root time scale with essentially constant memory in its simplest cycle-detection form.
2. Track every walk state algebraically
Represent a state as
(X,a,b) with X=g^a h^b.
If a transition multiplies X by g, update a. If it multiplies by h, update b. If it squares X, double both exponents.
The invariant X=g^a h^b must hold after every transition.
This coefficient bookkeeping is what turns a random collision into an equation for x.
3. A standard three-way iteration
Partition the group into three deterministic subsets S0,S1,S2 using a cheap function of X. Define:
if X in S0:
X ← X², a ←2a, b ←2b
if X in S1:
X ← Xg, a ←a+1
if X in S2:
X ← Xh, b ←b+1
All exponent updates are modulo N.
The partition should make the walk mix reasonably well. A poor partition can create short cycles or biased behaviour.
4. Why the walk is called rho-shaped
Iterating a deterministic function on a finite set eventually repeats a state value. The trajectory consists of a tail entering a cycle, visually like the Greek letter ρ.
For a sufficiently random-looking mapping on a set of size N, a collision is expected after on the order of √N steps by the birthday phenomenon.
Pollard’s insight was to exploit this collision without storing a table of every visited point.
5. Floyd cycle detection
Maintain two walkers:
tortoise ← f(tortoise) hare ← f(f(hare)).
When their group elements X agree, a collision has been found.
Only the two current states are required, so memory remains constant apart from arithmetic temporaries.
Other cycle-finding methods such as Brent’s algorithm can reduce function evaluations, but the collision equation is unchanged.
6. Derive the collision equation
Suppose two tracked states collide:
g^a h^b = g^A h^B.
Since h=g^x:
g^(a+bx)=g^(A+Bx).
Therefore
a−A ≡ x(B−b) (mod N).
This is a linear congruence for x.
7. Worked example in F101*
Take p=101. The element g=2 has order100. Let
h=55.
The hidden logarithm is x=37, but assume we do not know it.
Use the three-way rule determined by X mod3:
X mod3 = 0: square X mod3 = 1: multiply by g X mod3 = 2: multiply by h.
Starting both Floyd walkers at (1,0,0), the first collision in this deterministic toy run occurs after six tortoise steps.
8. The collision states
The two coefficient records are
tortoise: (X,a,b)=(64,10,8) hare: (X,A,B)=(64,48,34).
Both represent the same group element 64 modulo101.
Insert the coefficients into the collision equation:
10−48 ≡ x(34−8) (mod100) −38 ≡26x (mod100) 62 ≡26x (mod100).
9. The coefficient may not be invertible
We cannot simply invert26 modulo100 because gcd(26,100)=2.
Divide the congruence by two:
13x ≡31 (mod50).
Now 13 is invertible modulo50. Since 13^−1≡27 mod50:
x ≡31·27 ≡37 (mod50).
This gives two candidates modulo100:
x=37 or87.
Verification distinguishes them:
2^37 mod101 =55 2^87 mod101 =46.
Hence x=37.
10. General linear-congruence solving
From
c x ≡ d (mod N),
let r=gcd(c,N).
If r does not divide d, the collision bookkeeping is inconsistent with the assumed subgroup contract.
If r divides d, divide by r and solve modulo N/r. There are r solutions modulo N. Test each candidate against g^x=h or use additional collision information.
When N is prime, every nonzero c is invertible, so this complication disappears.
11. Degenerate collisions
A collision may yield c=0 and d=0 modulo N. Then the equation contains no information about x.
Restart with a different partition, seed or randomisation constant.
If c=0 but d≠0, something has broken in the invariant tracking or group-order assumptions because equal group states cannot imply a false exponent congruence.
12. Randomising the iteration
The simple three-way walk is excellent for teaching, but serious implementations use more partitions and precomputed multipliers to improve mixing.
For an r-adding walk, precompute group elements
M_i=g^(u_i)h^(v_i)
and partition states into r subsets. A step multiplies by the corresponding M_i and updates a,b by u_i,v_i.
The invariant remains transparent while the walk behaves more like a random mapping.
13. Negation maps and automorphisms
Some groups have efficiently computable automorphisms that identify several group elements as equivalent for the purpose of the walk.
Elliptic curves have point negation P→−P. Carefully quotienting by such symmetries can reduce the effective search space and improve constant factors.
However, canonicalisation must update the exponent coefficients consistently. A speed optimisation that breaks X=g^a h^b destroys the collision equation.
14. Distinguished points
Floyd’s method is memory-light but awkward to parallelise across many independent processors. Distinguished-point methods solve this.
Choose a cheaply recognised subset of group elements—for example, states whose representation has a certain number of leading zero bits. Each worker performs a random walk and stores only the states that hit distinguished points.
When two walks land on the same distinguished point, their coefficient records produce a collision equation.
15. Choosing the distinguished-point density
If distinguished points are too rare, walks travel a long time before reporting and failed workers lose more work. If too common, the central table grows large and communication overhead rises.
A density around 2^−t means roughly one in 2^t states is distinguished. The parameter t is tuned to memory, communication and worker count.
The recognition rule must be deterministic and uniform enough not to bias the walk severely.
16. Parallel rho
Give each worker a different random starting representation
X0=g^a0 h^b0.
All workers use the same iteration family or compatible randomisation. They report distinguished points to a shared collision table.
With enough independent walkers and adequate mixing, wall-clock time can decrease nearly linearly over a useful range, while total work remains on the generic √N scale.
17. Restart strategy
Rho is probabilistic. A walk can enter an unhelpful cycle or produce a degenerate collision.
A robust implementation treats restart as normal: change seed, partition constants or walk table and try again.
The algorithm should report attempts and iteration counts so that anomalously bad mixing can be diagnosed rather than hidden.
18. Pollard rho after Pohlig–Hellman
If the group order factors, first use Pohlig–Hellman. Then apply Pollard rho only to the large prime-order subgroup components.
This avoids wasting √N work when the actual hard subgroup has order q much smaller than N.
The two algorithms therefore compose naturally: decomposition outside, generic collision search inside.
19. Pollard rho on elliptic curves
For Q=[x]P, track states
R=[a]P+[b]Q.
A collision
[a]P+[b]Q=[A]P+[B]Q
gives
a−A ≡ x(B−b) mod N
when P has order N.
The coefficient algebra is exactly the same as in multiplicative groups.
20. Time–memory comparison with baby-step giant-step
Baby-step giant-step typically uses O(√N) group operations and O(√N) stored table entries.
Pollard rho uses O(√N) expected group operations but can operate with constant memory in cycle-detection mode or controlled memory in distinguished-point mode.
The price is probabilistic runtime, restarts and a more complicated parallel collision infrastructure.
21. Verification receipt
For a teaching or research implementation, retain:
group order N base g and target h partition / transition definition initial state(s) collision group element both (a,b) coefficient pairs linear congruence candidate solution(s) final g^x=h verification.
This makes the result independently auditable.
22. Common mistakes
1. Updating X without updating a,b. 2. Solving the collision congruence by modular inversion when the coefficient is not a unit. 3. Forgetting that exponents are modulo the order of g. 4. Using a partition that creates tiny deterministic cycles.
5. Treating a degenerate collision as a proof of failure. 6. Storing every point and losing rho’s memory advantage. 7. Parallelising without globally comparable distinguished points. 8. Accepting a congruence solution without checking g^x=h.
23. Practice set
1. State the tracked-state invariant. 2. Derive the collision equation. 3. Why is the expected collision scale √N? 4. What memory does Floyd detection need?
5. In the worked example, write the two colliding states. 6. Derive 26x≡62 mod100. 7. Why can 26 not be inverted mod100? 8. Find the two candidate exponents.
9. Which candidate is correct? 10. What is a degenerate collision? 11. What is an r-adding walk? 12. What is a distinguished point?
13. Why are distinguished points useful for parallelism? 14. Why should Pohlig–Hellman usually run first when N is factored? 15. How does rho translate to elliptic curves? 16. What is the simplest final certificate?
24. Answers
1. X=g^a h^b. 2. Equal states imply a−A≡x(B−b) modN. 3. Birthday collisions in a random-looking set of N states. 4. Two active states plus arithmetic temporaries.
5. (64,10,8) and (64,48,34). 6. −38≡26x, hence62≡26x mod100. 7. gcd(26,100)=2. 8. 37 and87 modulo100.
9. 37 because 2^37≡55 mod101. 10. A collision whose coefficient equation gives no usable information. 11. A multi-partition walk using precomputed multipliers g^u h^v. 12. A sparse, cheaply recognised subset of states stored for collision matching.
13. Independent workers can report sparse checkpoints to a shared table. 14. It reduces the search to the genuinely hard prime-order components. 15. Track R=[a]P+[b]Q and solve the same collision congruence. 16. Verify g^x=h.
Sources and further study
J. M. Pollard, Monte Carlo Methods for Index Computation (mod p), Mathematics of Computation 32(143), 1978, 918–924, introduces the rho method for discrete logarithms. Victor Shoup’s A Computational Introduction to Number Theory and Algebra provides a modern finite-group treatment.
Continue through Batch 07
Return to Guide 25: Pohlig–Hellman. Continue to Guide 27: Index Calculus and Guide 28: Number Field Sieve for Discrete Logarithms.