As noted on the previous page, the Elligator map to the Jacobi quartic, written in terms of the Ristretto parameters, is given by \[ (s,t) = \left( + \sqrt{ \frac{ a_2(r+1)(a_2 + d_2)(d_2 - a_2) }{ (d_2 r - a_2)(a_2 r - d_2) } } , \frac{ +a_2(r-1)(a_2 + d_2)^2 }{ (d_2 r - a_2)(a_2 r - d_2) } - 1 \right) \] or \[ (s,t) = \left( - \sqrt{ \frac{ a_2r(r+1)(a_2 + d_2)(d_2 - a_2) }{ (d_2 r - a_2)(a_2 r - d_2) } } , \frac{ -a_2r(r-1)(a_2 + d_2)^2 }{ (d_2 r - a_2)(a_2 r - d_2) } - 1 \right) \] depending on which square root exists, preferring the second when \(r = 0\) and both are square. (When using the ristretto255 parameters, the first is nonsquare when \(r = 0\) and there is no ambiguity).

Applying the isogeny \(\theta\) to \(s,t\) gives a point on \(\mathcal E_2\). When the denominator is zero, the Elligator result should be a 2-torsion point, but as noted in the Decaf paper it does not matter which one, since we quotient out by \(2\)-torsion anyways.

This can be implemented for ristretto255 with a single square root computation, using the sqrt_ratio_i function described in the explicit formulas section. To make this work, ristretto255 chooses \(n = i = +\sqrt{-1}\) as the quadratic nonresidue.

Write the numerator and denominator as \[ \begin{aligned} N_s &= a(r+1)(a + d)(d - a) \\ D &= (d r - a)(a r - d). \end{aligned} \] The value of \(s\) is then either \(+\sqrt{N_s/D}\) or \(-\sqrt{rN_s/D}\). Since \(r = ir_0^2\), we have \[ -\sqrt{\frac {rN_s} D} = -\sqrt{\frac {ir_0^2N_s} D} = -\left| r_0 \sqrt{i \frac {N_s} D} \right|. \]

Because we want to apply \(\theta\) to \((s,t)\), we can work projectively and write \(t = N_t/D\). Then \[ N_t = c(r-1)(a+d)^2 - D, \] where \(c = a\) in the first case where \(N_s/D\) is square and \(c = -ar\) in the second case where \(rN_s/D\) is square.

Applying \(\theta\) gives \[ (x,y) = \left( \frac { 2s } { t } \frac 1 { \sqrt{ad-1} } , \quad \frac { 1 +a s^2 } { 1 - as^2 } \right) = \left( \frac { 2s D } { N_t \sqrt{ad-1} } , \quad \frac { 1 + as^2 } { 1 - a s^2 } \right). \] In extended coordinates, this becomes \[ \begin{aligned} X &= (2sD)(1-as^2) \\ Y &= (1+as^2)(N_t \sqrt{ad-1})\\ Z &= (N_t \sqrt{ad-1})(1-as^2)\\ T &= (2sD)(1+as^2). \end{aligned} \]

In summary, we can compute the Elligator map directly to extended coordinates as follows.

1. \(r \gets ir_0^2\).
2. \(N_s \gets (r+1)(1-d^2) \textcolor{gray}{= a(r+1)(a+d)(a-d)} \).
3. \(c \gets -1\).
4. \(D \gets (c - dr)(r+d) \textcolor{gray}{= (dr -a)(ar-d)} \).
5. Ns_D_is_sq, \(s \gets \) sqrt_ratio_i(N_s, D).
6. \(s' \gets -|s r_0|\).
7. \(s \gets s' \) if not Ns_D_is_sq.
8. \(c \gets r \) if not Ns_D_is_sq.
9. \(N_t \gets c(r-1)(d-1)^2 - D\).
10. \(W_0 \gets 2sD \).
11. \(W_1 \gets N_t\sqrt{ad-1} \).
12. \(W_2 \gets 1 - s^2 \textcolor{gray}{= 1 +as^2} \).
13. \(W_3 \gets 1 + s^2 \textcolor{gray}{= 1 -as^2} \).
14. Return \( (W_0 W_3 : W_2 W_1 : W_1 W_3 : W_0 W_2) \).

When \(D = 0\), we need to obtain a \(2\)-torsion point, but since sqrt_ratio_i returns (0, 0), the resulting Edwards point will be the identity \((0,1)\), so the exceptional case does not need to be handled specially.