Elligator
Define \(\chi : \text{F}_q \to \text{F}_q\) by \(\chi (a) = a^{(q - 1) / 2}\) with a prime power \(q \equiv 3 \pmod{4}\).
The function \(\chi \) is called a \(\textbf{quadratic character}\).
Let \(q\) be a prime power congruent to \(3\) modulo \(4\). Let \(s\) be a nonzero element of \(\text{F}_q\) with \((s^2 - 2) (s^2 + 2) \neq 0\).
Define \(c = 2 / s^2\).
In the situation of the definition of \(c\).
Then \(c (c - 1) (c + 1) \neq 0\).
TODO
In the situation of the definition of \(c\).
Define \(r = c + 1 / c\).
In the situation of the definition of \(r\).
Then \(r \neq 0\).
TODO
In the situation of the definition of \(c\).
Define \(d = - (c + 1)^2 / (c - 1)^2\).
In the situation of the definition of \(d\).
Then \(d\) is not a square.
TODO
Let \(t \in \text{F}_q \setminus \{ \pm 1 \} \).
Define \(u = (1 - t) / (1 + t)\).
In the situation of the definition of \(u\).
Then \(u \neq 0\).
TODO
In the situation of the definition of \(u\).
Then \(u\) is defined.
TODO
In the situation of the definitions of \(u\) and \(r\). Let \(t \in \text{F}_q \setminus \{ \pm 1 \} \).
Define \(v = u^5 + (r^2 - 2) u^3 + u\).
TODO
In the situation of the definition of \(v\).
Then \(v \neq 0\).
TODO
In the situation of the definitions of \(u\) and \(v\). Let \(t \in \text{F}_q \setminus \{ \pm 1 \} \).
Define \(X = \chi (v) u\).
TODO
In the situation of the definition of \(X\).
Then \(X \neq 0\).
TODO
In the situation of the definitions of \(c\), \(u\) and \(v\). Let \(q\) be a prime power congruent to \(3\) modulo \(4\). Let \(t \in \text{F}_q \setminus \{ \pm 1 \} \).
Define \(Y = ( \chi (v) v )^{(q + 1) / 4} \chi ( v ) \chi (u^2 + 1 / c^2)\).
In the situation of the definition of \(Y\).
Then \(Y \neq 0\).
TODO
In the situation of the definitions of \(c\), \(X\), \(s\) and \(Y\). Let \(q\) be a prime power congruent to \(3\) modulo \(4\). Let \(t \in \text{F}_q \setminus \{ \pm 1 \} \).
Define \(x = (c - 1) s X (1 + X) / Y\).
In the situation of the definition of \(x\).
Then \(x\) is defined.
TODO
In the situation of the definition of \(x\).
Then \(x \neq 0\).
TODO
In the situation of the definitions of \(r\) and \(X\). Let \(q\) be a prime power congruent to \(3\) modulo \(4\). Let \(t \in \text{F}_q \setminus \{ \pm 1 \} \).
Define \(y = (r X - (1 + X)^2) / (r X + (1 + X)^2)\).
In the situation of the definition of \(y\).
Then \(y\) is defined.
TODO
In the situation of the definition of \(y\).
Then \(y \neq 0\).
TODO
In the situation of the definitions of \(u\), \(v\), \(X\), \(Y\), \(x\) and \(y\).
Then \(uvXYx (y + 1) \neq 0\).
TODO
In the situation of the definitions of \(X\), \(Y\) and \(r\).
Then \(Y^2 = X^5 + (r^2 - 2) X^3 + X\).
TODO
In the situation of the definitions of \(x\), \(y\) and \(d\).
Then \(x^2 + y^2 = 1 + d x^2 y^2\).
TODO
In the situation of Theorem 1, the decoding function for the complete Edwards Curve \(E : x^2 + y^2 = 1 + d x^2 y^2\) is the function \(\phi : \text{F}_q \to E(\text{F}_q)\) defined as follows:
\(\phi (\pm 1) = (0, 1)\); \(\text{if } t \notin \{ \pm 1\} , \quad \text{then} \quad \phi (t) = (x, y)\).
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO