Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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