I'm currently on KSS-16 curves, which are given by $\newcommand{\F}{\mathbb F}E(\F_p):\ y^2=x^3+x$. In an actual paper for updating the key sizes, there is a twist of $E$ defined, given by $E'(\F_{p^2}):\ y^2=x^3+2^{1/4}x$. [4] I would like to understand how they come to that twist, and how to define the homomorphism or isomorphism $E\to E'$.
My attempt is the following: I thought about using $\F_{p^{16}}\cong \F_{p^2}[x]/(x^8-2^{1/2})$. Choosing $u\in \F_{p^{16}}$ such that $u^8=2^{1/2}$ leads to: $u=2^{1/16}$. Now I don't know how to get further or what to aim. There is a small hole in my notes and I can't find anything to fit.
Details
[1] solves the primary question, where [2] throws up an extended question: Are twists usable for speeding up by the GLV/GLS Method?
Required stuff
We could consider the affine equation for an elliptic curve and use proposition X.5.4 from [3] or the projective way, given in [1] on page 138 ff. and use a dehomogenization. The problem I've met is, that Silverman only define twists of degree 2,3,4 and 6. But this time, this is a twist of degree eight. (Octic twist?) Let me repeat the given stuff first:
Preliminaries
- Elliptic Curve $E(\F_p):\ y^2=x^3+x$
- Prime $p\equiv \pm 3\bmod 8$
- Twist $E'(\F_{p^2}):\ y^2=x^3+2^{1/4}x$
- Embedding degree $k=16$
- Discriminant $D=1$
- $j$-Invariant: $j_E=12^3$
Definition 1: Degree of a Twist
Let $E(\F_p)$ be an elliptic curve. The degree of its twist $E'(\F_{p^{k/d}})$ is defined by the integer $d$.
Proposition 2: [3] Prop. X.5.4
Let $char(\F_p)>3$ and let
$n=\begin{cases} 2 & if j_E\neq 0,12^3\\ 4 & j_E=12^3\\ 6 & j_E=0.\end{cases}$
Then the twists of E are canonically isomorphic over the algebraic closure of $\F_p$. More precisely, in our situation of $E$, we have the twist $E'_d$ corresponding to $m\in\F_p^*$ given by:
(i) $E'_m:\ y^2=x^3+m^2Ax+m^3B$ if $n=2$
(ii) $E_m:\ y^2=x^3+mAx$ if $n=4$ and
(iii) $E_m:\ y^2=x^3+mB$ if $n=6$.
Proposition: Projective version [1]
Let $E:\ Y^2Z=X^3+AXZ^2+BZ^3$ with $A,B\in\F_p$. For any $d\in\F_p^*$ all twists of $E$ corresponding to $d$ are given by: $E_d:\ dY^2Z=X^3+AXZ^2+BZ^3$ or by change of variables $dZ\leftrightarrow Z$ $E_d:\ Y^2=X^3 + \frac{A}{d^2}XZ^2 + \frac{B}{d^3}Z^3$ which becomes isomorphic to $E$ over any field, where $d$ is a square.
Application
We have $E:\ y^2=x^3+x$, that means $A=1, B=0$. Furthermore, the Twist, we want to reach is given by $E':\ y^2=x^3+2^{1/4}x$. Therefore $m=2^{1/8}$ and $d=(1/2)^{1/8}$. The missing degree eight twist is the only obstacle right now. But, if we consider $\F_{p^{16}}\cong \F_{p^2}[t]/(t^8-2)$, we would get the equation $t^8=2$, where $t\in\F_{p^{16}}$ and 2 should be not a square in $\F_{p^2}$, but indeed $\sqrt{2}\in\F_{p^2}$, since $2\in\F_p$ is a non-square if $p\equiv \pm 3 \bmod 8$ and we have $\F_{p^{16}} \cong \F_p[X]/(X^{16}-2)$.
Missing Answere
Is this an octic twist as given in [4, Section 6.3]? How to compute it then? I thought about $t^8=\sqrt{2}$ which would lead to $t=2^{1/16}$ and, therefore, $E_t:\ Y^2=X^3 + 2^{1/8}XZ^2$, what is not $2^{1/4}$. If this is a typo and, therefore, a quartic twist, it is solved then.
References
[1] http://www.jmilne.org/math/Books/ectext5.pdf p.138
[2] https://eprint.iacr.org/2008/194.pdf
[3] https://link.springer.com/book/10.1007%2F978-0-387-09494-6