pollard rho

Work in Progress

Concept

Pollard rho

Collision
f(a,b) = g^a h^{-b}

(a,b) != (a’,b’) st. f(a,b) = f(a’,b’)

Correctness claim (Pollard rho collision equation). A collision gives .

  • layman explanation: equal walk states make one linear modular equation for the unknown logarithm.

Proof.

Pollard rho walks through elements until a collision gives

but collision finding is still space

When is invertible modulo , this yields . It has expected time and constant memory using cycle detection.