pollard rho
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
but collision finding is still
When