# Inversion Free Direct Conversion between Twisted Edwards (X,Y,Z) and Montgomery (X,Z)

The Wikipedia page for Montgomery curves shows how to convert points on a twisted Edwards curve to and from points on an equivalent Montgomery curve. However, their description and the original twisted Edwards curve paper use affine coordinates for the conversion.

Is it possible to convert directly from projective twisted Edwards coordinates (X,Y,Z) to projective Montgomery coordinates (X,Z) and back without expensive inversions in the underlying field $\mathbb{F}_p$? Does anybody know explicit formulas for this or a method on how to produce the projective equivalent of the description found on Wikipedia?

The ultimate goal is to convert to Montgomery points with as little cost as possible, do the scalar multiplication using cheap Montgomery arithmetic and at the end convert the point back to twisted Edwards coordinates.

The conversion formula from twisted Edwards to Montgomery form is:

$$x_{mont} = \frac{X_{mont}}{Z_{mont}}= \frac{1+y_{ed}}{1-y_{ed}} = \frac{1+\frac{Y_{ed}}{Z_{ed}}}{1-\frac{Y_{ed}}{Z_{ed}}} = \frac{Z_{ed}+Y_{ed}}{Z_{ed}-Y_{ed}}$$

If you want the affine $x_{mont}$, you need to compute the inversion. But if you just need $X_{mont}$ and $Z_{mont}$ you can skip the inversion, since the nominator is X and the denominator Z.

$$X_{mont} = Z_{ed}+Y_{ed}$$ $$Z_{mont} = Z_{ed}-Y_{ed}$$

1. If you use $Z \neq 1$ as input for the Montgomery ladder, this will increase the cost of this scalar multiplication by more than the cost of an initial inversion (about 10% of the ladder cost).
4. When using the cheap X,Z Montgomery ladder and convert back to twisted Edwards, you get $Y$ and $Z$. You can recover $|X|$ from that using the curve equation (essentially a point decompression, cost similar to a field inversion), but you don't know the sign of $X$.
• Regarding point 4.: Is it possible to have the same sign for the $X$ coordinate after the Montgomery ladder as compared to doing the computations with twisted Edwards coordinates? Not having the sign of the $X$ coordinate, is there value in doing scalar multiplication this way? – tobiasfar May 20 '15 at 11:56