In the situation of Theorem 1, \(c = 2/s^2\) satisfies

In the situation of Theorem 1, \(r = c + 1/c \neq 0\): if \(r = 0\) then \(c = -1/c\), so \(c^2 = -1\), a contradiction since \(-1\) is not a square in \(\mathbb {F}_q\).

In the situation of Theorem 1, \(d = -(c + 1)^2/(c - 1)^2\) is not a square in \(\mathbb {F}_q\): otherwise \(-1 = d(c - 1)^2/(c + 1)^2\) would be a square, a contradiction.

The neutral point \((0, 1)\), which is the value of \(\varphi (\pm 1)\) in Definition 2, lies on the complete Edwards curve \(E : x^2 + y^2 = 1 + d x^2 y^2\).

In the situation of Theorem 1, \(u = (1 - t)/(1 + t) \neq 0\) for \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \), since \(1 - t \neq 0\) and \(1 + t \neq 0\).

In the situation of Theorem 1, \(v \neq 0\).

In the situation of Theorem 1, \(X = \chi (v)u \neq 0\), since \(u \neq 0\) and \(\chi (v) \neq 0\).

In the situation of Theorem 1, \(XY \neq 0\); in particular \(Y \neq 0\), so \(x = (c - 1)sX(1 + X)/Y\) is defined.

In the situation of Theorem 1, \(1 + X \neq 0\): if \(X = -1\) then \(u = -\chi (v)\), so \(v = -\chi (v)r^2\) and hence \(\chi (v) = -\chi (v)\), a contradiction.

In the situation of Theorem 1, \(x = (c - 1)sX(1 + X)/Y \neq 0\), since \(c \neq 1\), \(s \neq 0\), \(X \neq 0\) and \(1 + X \neq 0\).

In the situation of Theorem 1, for each \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \) the denominator of

is nonzero, i.e. \(1 + t \neq 0\).

In the situation of Theorem 1, the quantity

is defined for each \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \), since \(c^2 \neq 0\).

In the situation of Theorem 1, \(Y \neq 0\) for each \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \), so that

is defined.

In the situation of Theorem 1, \(rX + (1 + X)^2 \neq 0\) for each \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \), so that

is defined.

In the situation of Theorem 1, let \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \) and let \(r\), \(X\), \(Y\) be as above. Then

In the situation of Theorem 1, let \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \) and let \(u, v, X, Y, x, y\) be as above. Then

In the situation of Theorem 1, let \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \) and let \(x\), \(y\) be as above. Then \((x, y)\) is a point of the complete Edwards curve \(E : x^2 + y^2 = 1 + d x^2 y^2\), i.e.

The forward part of statement 2 of Theorem 3: every \((x, y) \in \varphi (\mathbb {F}_q)\) satisfies \(y + 1 \neq 0\); \((1 + \eta r)^2 - 1\) is a square, where \(\eta = (y - 1)/(2(y + 1))\); and if \(\eta r = -2\) then \(x = 2s(c - 1)\chi (c)/r\).

With \(b = \lfloor \log _2 q \rfloor \) we have \(2^b \leq q\); hence the integers \(0, 1, \ldots , 2^b - 1\) are distinct in \(\mathbb {F}_q\).

Distinct bit strings of length \(n\) have distinct binary values \(\sum _i \tau _i 2^i\).

Every integer \(m\) with \(0 \leq m {\lt} 2^n\) is the binary value of some bit string of length \(n\).

Let \(q\) be prime and let \(a, b \in \{ 0, 1, \ldots , (q-1)/2\} \) with \(a = -b\) in \(\mathbb {F}_q\). Then \(a = b\). This is the step of Theorem 4 that removes the sign ambiguity of \(\varphi \).

Since \(2^b \leq q\), the integers \(0, 1, \ldots , 2^b - 1\) are distinct in \(\mathbb {F}_q\); hence \(\sigma \) is injective.

Since \(2^b {\gt} q/2\), the set \(\{ 0, 1, \ldots , (q-1)/2\} \) is a subset of \(\{ 0, 1, \ldots , 2^b - 1\} \); hence each of \(0, 1, \ldots , (q-1)/2\) has a preimage under \(\sigma \), lying in \(S\).

For every \(t \in \mathbb {F}_q\), at least one of \(t, -t\) lies in \(\{ 0, 1, \ldots , (q-1)/2\} = \sigma (S)\); that is, there is \(\tau \in S\) with \(\sigma (\tau ) = t\) or \(\sigma (\tau ) = -t\).

For \(t \in \mathbb {F}_q\), the parameter \(\bar t\) reconstructed from \(\varphi (t)\) in Theorem 3.3 satisfies \(\bar t = t\) or \(\bar t = -t\). This is the key step showing that \(\varphi (t)\) has no preimages besides \(t\) and \(-t\).

The forward part of statement 1 of Theorem 3: for every \(t \in \mathbb {F}_q\),

The reverse part of statement 1 of Theorem 3: for \(t \in \mathbb {F}_q\), no element of \(\mathbb {F}_q\) other than \(t\) and \(-t\) is a preimage of \(\varphi (t)\) under \(\varphi \).

The reverse part of statement 2 of Theorem 3: every \((x, y) \in E(\mathbb {F}_q)\) such that \(y + 1 \neq 0\); \((1 + \eta r)^2 - 1\) is a square, where \(\eta = (y - 1)/(2(y + 1))\); and \(x = 2s(c - 1)\chi (c)/r\) whenever \(\eta r = -2\), lies in \(\varphi (\mathbb {F}_q)\).

In the situation of Definition 2: if \(t \in \mathbb {F}_q\) then the set of preimages of \(\varphi (t)\) under \(\varphi \) is \(\{ t, -t\} \). Equivalently, \(\varphi (t) = \varphi (-t)\) if and only if no element of \(\mathbb {F}_q\) other than \(t\) and \(-t\) maps to \(\varphi (t)\).

In the situation of Definition 2: \(\varphi (\mathbb {F}_q)\) is the set of \((x, y) \in E(\mathbb {F}_q)\) such that

• \(y + 1 \neq 0\);

• \((1 + \eta r)^2 - 1\) is a square, where \(\eta = \frac{y - 1}{2(y + 1)}\); and

• if \(\eta r = -2\) then \(x = 2s(c - 1)\chi (c)/r\).

In the situation of Definition 2: if \((x, y) \in \varphi (\mathbb {F}_q)\) then the following elements \(\bar X, z, \bar u, \bar t\) of \(\mathbb {F}_q\) are defined and \(\varphi (\bar t) = (x, y)\):

For \((x, y) \in \varphi (\mathbb {F}_q)\) the denominator \(2(y + 1)\) of \(\eta \) is nonzero, so \(\eta \) and hence \(\bar X\) of Theorem 3.3 are defined.

The denominator \(c^2\) occurring in \(z\) of Theorem 3.3 is nonzero, so \(z\) is defined.

For \((x, y) \in \varphi (\mathbb {F}_q)\) the denominator \(1 + \bar u\) of \(\bar t\) in Theorem 3.3 is nonzero, so \(\bar t\) is defined.

Since \(2^b \leq q\) and \(2^b {\gt} q/2\), each of \(0, 1, \ldots , (q-1)/2\) has a preimage under \(\sigma \), and the binary values of the strings in \(S\) are exactly

Binary evaluation is injective, hence

For \(q \equiv 3 \pmod4\), the set \(S\) has exactly

elements.

In the situation of Theorem 4, the set of admissible strings satisfies

In the situation of Theorem 4, \(\iota \) is an injective map from \(S\) to \(E(\mathbb {F}_q)\).

In the situation of Theorem 4, \(\iota (S) = \varphi (\mathbb {F}_q)\).

Combining the injectivity of \(\iota \) with \(\iota (S) = \varphi (\mathbb {F}_q)\): the map

is a bijection.

Let \(p\) be a natural number and let \(L\) be a list of primes with \(\prod _{r \in L} r = p - 1\). If there is an \(a\) with \(a^{p-1} \equiv 1 \pmod p\) and \(a^{(p-1)/r} \not\equiv 1 \pmod p\) for every \(r \in L\), then \(p\) is prime.

The number \(q = 2^{251} - 9\) is prime.

The characteristic satisfies \(q \equiv 3 \pmod4\), so the standing hypotheses of Elligator 1 are met by \(\mathbb {F}_q\).

The element \(s\) is nonzero and satisfies \((s^2 - 2)(s^2 + 2) \neq 0\).

With \(s\) as above, \(c = 2/s^2\) equals

With \(c\) as above, \(r = c + 1/c\) equals

With \(c = 2/s^2\) as above,

so the complete Edwards curve of Theorem 1 and Definition 2 for this choice of \((q, s)\) is exactly Curve1174, \(x^2 + y^2 = 1 - 1174 x^2 y^2\).

The quadratic character of the Edwards coefficient satisfies \(\chi (d) = -1\).

The coefficient \(-1174\) is a non-square in \(\mathbb {F}_q\); this is the criterion of [bernstein2013a, Theorem 3.3] making Curve1174 a complete Edwards curve.

For every \(t \in \mathbb {F}_q\) the point \(\varphi (t)\) lies on Curve1174.

For Curve1174 the string length of Theorem 4 is \(b = \lfloor \log _2 q \rfloor = 250\).

For Curve1174 the string encoding \(\iota \) is a bijection from \(S\) onto \(\varphi (\mathbb {F}_q)\).

The point \((U, V) = (4, V)\) lies on the Montgomery curve

The point \((4/V, 3/5)\) satisfies the Curve1174 equation.