# Affine and Jacobian (x, w) Coordinates

In $$(x, w)$$ coordinates, the curve equation becomes: $w^2 x = x^2 + ax + b$ The neutral $$N$$ does not have a defined affine $$w$$ coordinate. For points in $$\mathbb{G}$$ other than $$N$$, the $$w$$ coordinates is non-zero.

## Encoding and Decoding

Encoding of $$(x, w)$$ is a simple encoding of the $$w$$ coordinate.

Decoding proceeds as follows:

• If $$w = 0$$, then return the point $$N$$.

• Solve for $$x$$ the equation $$x^2 - (w^2 - a)x + b = 0$$:

• Compute $$\Delta = (w^2 - a)^2 - 4b$$ (which is necessarily non-zero).
• If $$\Delta$$ is not a quadratic residue, then there is no solution (the provided encoding is invalid). Otherwise, there are two solutions for $$x$$, depending on which square root of $$\Delta$$ is used: $x = \frac{w^2 - a \pm \sqrt{\Delta}}{2}$
• Exactly one of the two solutions is a quadratic residue; use the other one.

## Affine Coordinates

Given points $$P_1 = (x_1, w_1)$$ and $$P_2 = (x_2, w_2)$$ in $$\mathbb{G}$$, their sum in the group $$P_3 = (x_3, w_3) = P_1 + P_2$$ is computed with: $\begin{eqnarray*} x_3 &=& \frac{b x_1 x_2 (w_1 + w_2)^2}{(x_1 x_2 - b)^2} \\ w_3 &=& -\frac{(w_1 w_2 + a)(x_1 x_2 + b) + 2b(x_1 + x_2)}{(w_1 + w_2)(x_1 x_2 - b)} \end{eqnarray*}$

These formulas are unified: they work properly for all points except when $$P_1$$, $$P_2$$ or $$P_3$$ is the neutral $$N$$.

Specialized doubling formulas, to compute the double $$(x', w')$$ of the point $$(x, w)$$: $\begin{eqnarray*} x' &=& \frac{4bw^2}{(2x + a - w^2)^2} \\ w' &=& - \frac{w^4 + (4b-a^2)}{2w(2x + a - w^2)} \end{eqnarray*}$

Again, these formulas are only unified, since $$N$$ does not have a defined $$w$$ coordinate. Note that if the input point $$P$$ is not $$N$$, then its double $$2P$$ is not $$N$$ either, since the group $$\mathbb{G}$$ has odd order $$r$$.

## Jacobian Coordinates

Jacobian coordinates represent point $$(x, w)$$ as the triplet $$(X{:}W{:}Z)$$ with $$x = X/Z^2$$ and $$w = W/Z$$. The point $$N$$ is represented by $$(0{:}W{:}0)$$ for any $$W \neq 0$$. Jacobian coordinates correspond to an isomorphism between curve $$E(a, b)$$ and curve $$E(aZ^2, bZ^4)$$.

The addition of $$P_1 = (X_1{:}W_1{:}Z_1)$$ with $$P_2 = (X_2{:}W_2{:}Z_2)$$ into $$P_3 = (X_3{:}W_3{:}Z_3)$$ is obtained with the following: $\begin{eqnarray*} X_3 &=& b X_1 X_2 (W_1 Z_2 + W_2 Z_1)^4 \\ W_3 &=& -((W_1 W_2 + a Z_1 Z_2)(X_1 X_2 + b Z_1^2 Z_2^2) + 2b Z_1 Z_2 (X_1 Z_2^2 + X_2 Z_1^2)) \\ Z_3 &=& (X_1 X_2 -b Z_1^2 Z_2^2)(W_1 Z_2 + W_2 Z_1) \end{eqnarray*}$ These formulas can be computed with cost 8M+6S. If using Chudnovsky coordinates $$(X{:}W{:}Z{:}Z^2)$$ (i.e. we also keep around the value $$Z^2$$ in addition to $$Z$$), then cost is lowered to 8M+5S, but in-memory representation is larger.

Addition formulas are unified, because they do not compute the correct result when one or both of the operands are equal to $$N$$. However, if $$P_1 \neq N$$ and $$P_2 = -P_1$$, then a valid representation of $$N$$ is computed. Thus, the only exceptional cases that must be handled in an implementation are $$P_1 = N$$ and $$P_2 = N$$. These two cases can be handled inexpensively with a couple of conditional copies, to obtain a complete routine which induces no tension between security and performance.

For doubling point $$(X{:}W{:}Z)$$ into $$(X'{:}W'{:}Z')$$, formulas are: $\begin{eqnarray*} X' &=& 16bW^4 Z^4 \\ W' &=& -(W^4 + (4b-a^2)Z^4) \\ Z' &=& 2WZ(2X + aZ^2 - W^2) \end{eqnarray*}$ These formulas are complete: they work properly for all inputs, including the neutral element $$N$$.

Generic implementation of point doubling is easily done in cost 2M+5S. If the base field is such that $$q = 3\bmod 4$$, then $$4b - a^2$$ is a square, and, provided that we have $$e = \sqrt{4b - a^2}$$ and that the constant $$e$$ is small, then we can compute $$W'$$ as $$(e/2)(2WZ)^2 - (Z^2 + eW^2)^2$$, which leads to an implementation in cost 1M+6S.

More interestingly, if parameters are such that $$-a$$ is a square, and that $$2b = a^2$$, then we can obtain an implementation of doubling in cost 2M+4S. Analysis shows that such a situation can happen only if $$q = 3\bmod 8$$, and there will be a single curve (up to isomorphism) that matches these conditions; we can thus assume that the curve parameters are $$a = -1$$ and $$b = 1/2$$. In that case, the point doubling algorithm becomes the following:

1. $$t_1 \leftarrow WZ$$
2. $$t_2 \leftarrow t_1^2$$
3. $$X' \leftarrow 8 t_2^2$$
4. $$t_3 \leftarrow (W + Z)^2 - 2t_1$$
5. $$W' \leftarrow 2t_2 - t_3^2$$
6. $$Z' \leftarrow 2t_1 (2X - t_3)$$

Successive doublings rely on the definition of some isogenies: $\begin{eqnarray*} \psi_\pi : E(a, b) &\longrightarrow& E(-2a\pi^2, \pi^4(a^2-4b))[r] \\ (x, w) &\longmapsto& \left(\pi^2 w^2, -\frac{\pi (x - b/x)}{w}\right) \end{eqnarray*}$ for a constant $$\pi \neq 0$$ (and defining that the image of the point-at-infinity and the image of $$N$$ are both the point-at-infinity in the target curve). These functions are isogenies on the curves (that is, using classic point addition) and the image is the subgroup of points of $$r$$-torsion in the destination curve. If two constants $$\pi$$ and $$\pi'$$ are such that $$2\pi\pi' = 1$$, then for any $$P \in E(a, b)$$, $$\psi_{\pi'}(\psi_{\pi}(P)) = 2P$$. In other words, composing the two isogenies brings us back to the original curve, and together they compute a point doubling (on the curve).

To obtain a similar effect with our group $$\mathbb{G}$$, we also define the following functions: $\begin{eqnarray*} \theta_\pi : E(a, b) &\longrightarrow& \mathbb{G}(-2a\pi^2, \pi^4(a^2-4b)) \\ (x, w) &\longmapsto& \left(\frac{\pi^2(a^2-4b)}{w^2}, \frac{\pi (x - b/x)}{w}\right) \end{eqnarray*}$ using the notation that $$\mathbb{G}(a, b)$$ is our prime order group, defined over a base double-odd elliptic curve with parameters $$a$$ and $$b$$. With these functions, we get that both $$\theta_{1/2}(\psi_1(P))$$ and $$\theta_{1/2}(\theta_1(P))$$ compute the double (in $$\mathbb{G}$$) of point $$P$$.

We can then compute a succession of doublings by a sequence of invocations of these functions, freely switching between $$\psi$$ and $$\theta$$ as best suits computations, in order to minimize cost. This yields complete formulas; the neutral $$N$$ is represented by $$(0{:}W{:}0)$$ for any $$W \neq 0$$, and the point-at-infinity (which will appear whenever applying a $$\psi$$ function on the neutral $$N$$) is represented by $$(W^2{:}W{:}0)$$ for any $$W \neq 0$$. Using these techniques, we can obtain the following costs for computing $$n$$ successive doublings, depending on the base field and the curve parameters:

• $$n$$(2M+5S) (for all curves)
• $$n$$(1M+6S) (if $$q = 3\bmod 4$$)
• $$n$$(4M+2S)+1M (if $$q = 3$$ or $$5\bmod 8$$)
• $$n$$(1M+5S)+1S (if $$a = 0$$)
• $$n$$(2M+4S) (if $$a = -1$$ and $$b = 1/2$$)

Please refer to the whitepaper (section 4.1) for additional details on these formulas.