# Parallelized Pollard's Rho algorithm for ECDLP + Jacobian coordinates

My implementation of the parallelized Pollard's Rho algorithm is using Jacobian coordinates to avoid the costly inversion operation when performing point addition.

I am wondering if there are any methods to check for distinguished points while in Jacobian form, since switching back to affine coordinates requires an inversion?

-

The bad news is that projective coordinates do not work with Pollard's Rho like you want it to. Rho needs an unambiguous point representation to find meaningful collisions, and in projective coordinates each point can have up to $p-1$ valid distinct representations.

The good news is that, sticking to affine coordinates, you can avoid most of the cost of the inversions by performing a bunch of them in parallel, and trading $N$ inversions by $1$ inversion plus $3N-3$ multiplications. This is the so-called Montgomery trick (Section 2.5.1), and is the most common approach in ECDLP Rho implementations.

-
Gah, I was afraid of that. When going from Jacobian -> Affine, $X' = X/Z^2$, does computing $X' = XZ^2$ remove the ambiguity? Could the distinguished point test be performed on that value? –  user13741 Jun 19 at 17:38
That should work (modulo a few unlikely corner cases). But keep in mind that will still be slower than affine with batch inversions; for a large enough batch, an inversion costs 3 multiplications, and affine coordinates look much better performance-wise than Jacobian, even assuming the DP check is free. –  Samuel Neves Jun 19 at 18:26