Uncomputing projective coordinates

Question

I am having a hard time understanding how to convert from projective coordinates, back to affine.

I am trying to compute point addition for Edward curves. Say we have the following: $$\begin{align} x_i &= X_i/Z_i\\ y_i &= Y_i/Z_i\\ A &= Z_1*Z_2\\ B &= A^2\\ C &= X_1*X_2 \\ D &= Y_1*Y_2 \\ E &= d*C*D\\ F &= B-E\\ G &= B+E\\ X_3 &= A* F*((X_1+Y_1)*(X_2+Y_2)-C-D)\\ Y_3 &= A* G*(D-C)\\ Z_3 &= c* F*G\\ \end{align}$$

[Editor's note: equations match hyperelliptic.org's add-2007-bl]

Now after obtaining values for $X_3$ and $Y_3$, to get back to affine coordinates, would I have to compute $X_3/Z_3$ and $Y_3/Z_3$ to get $(x_3,y_3)$ ?

Answer 1

Yes, after obtaining values for $X_3$ and $Y_3$ (and $Z_3$), in order to get back to affine coordinates, one would have to compute $X_3/Z_3$ and $Y_3/Z_3$ to get $(x_3,y_3)$.

However, in most cryptographic applications, we're making point multiplication with a large multiplier, which requires many point additions, which can be carried entirely in projective coordinates. We get back to affine coordinates only at the end of that. Therefore, the field inversion required to get back to affine coordinates is performed once per point multiplication, and represents a low proportion of the computational cost.

Whatever the base field, one can use the extended Euclidean algorithm to compute $1/Z_3$; or better the half-extended version there, which is specialized for the inverse; or $1/Z_3={Z_3}^{p-2}$ where $p$ is the number of elements in the base field. For the base field $\mathbb Z_p$ with $p$ prime, there's also the half-extended binary GCD algorithm there.

Answer 2

would I have to compute X3/Z3X3/Z3 and Y3/Z3Y3/Z3 to get (x3,y3)(x3,y3)

Yes. The way you do division here is multiplying the nominator with the Modular_multiplicative_inverse of the denominator.

Note that a naive implementation of extended euclidean is vulnerable to side-channel attacks, so using exponentiation using a hardcoded addition chain is often preferred for computing the inverse.