5
$\begingroup$

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?

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – user13741
    Jun 19, 2014 at 17:38
  • $\begingroup$ 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. $\endgroup$ Jun 19, 2014 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.