[Math] Twists of an Elliptic Curve over Finite Fields

Question

I am working on the curve $secp256k1$ and want to understand the theory of twists of a curve over a finite field. (Especially an elliptic curve of the form $E: y^2 = x^3 + b$ over a finite field $K$) and have several questions about it.

To start with, I would like to understand the connection between the Automorphism group and the twists of an elliptic curve.
I read in Silverman's ''Arithmetic of Elliptic Curves'' that
$$Twist(E/K)\cong K^*/(K^*)^n, \text{ where } n=\#Aut(E)$$
In chapter X.5 Corollary 5.4.1 he further writes:
$$Twist(E/K)=H^1(G_{\bar{K}/K},Aut(E))\cong H^1(G_{\bar{K}/K},\mu_n)\cong K^*/(K^*)^n.$$
But I am not familiar with the notation of $H^1$ and do not understand what this statement really means. (In Chapter III Corollary 10.2 it says that there exists a natural isomorphism of $G_{\bar{K}/K}$-modules $Aut(E)\cong \mu_n$.)

Secondly I would like to know what all the twists of an elliptic curve of the form $E: y^2 = x^3 + b$ look like, but I mostly find explainations about the quadratic twist and not much about the others.
But since $j(E)=0$ for a curve of this form we have $\#Twist(E/K)=6$ right? What would the set $Twist(E/K)$ look like?
It would already contain the curve itself and the one unique quadratic twist right?

I will try to explain what I found out so far. I saw that there exists as well cubic and sextic twists.
Is it right, that the cubic twist of $E$ has the form
$E^{d_3}: y^2 = x^3 + b D^2$ for $D\in K^*$ cube free? With $\phi:E(K)\to E^{d_3}(K)$ by $(x,y)\mapsto (\frac{x}{D^{2/3}},\frac{y}{D})$.
What will be the form of the sextic twist? In ''Elliptic curves a computational approach'' it says $E^{d_6} : y^2 = x^3 + b d^j$ with $j=0,…,5$ and $d\not=0$ in $K$. But this seems weird since this also includes the quadratic twist no?

Answer 1

• Fix an elliptic curve $E$ defined over some field $K$ of characteristic $\ne 2,3$. This is the case with the curve secp256k1, built for the prime $$ p = 2^{256} - 4294968273\ .$$ In my case, the curve has the equation $y^2 = x^3+7$. But in general, there exist (after reparametrization), an equation of the shape $$ y^2=x^3+ax+b$$
• What is $\text{Aut}(E)$? This is the subset of the "Hom" in the category of varieties of the non-trivial morphisms $E\to E$, respecting $O$ and the group structure, defined over the base field $K$, which are invertible.

Let us consider a slightly more general case, an endomorphism, $E'\to E$, for two different elliptic curves, which preserve the origins, $O'\to O$. Notations are appropriate.

Such a morphism is given by a rational function $$ \begin{array}{rcl} E' &\longrightarrow &E \\ \text{Spec } \Bbb F_p[\xi,\eta]/(-\eta^2+\xi^3 +a'\xi+b') &\longrightarrow &\text{Spec } \Bbb F_p[x,y]/(-y^2+x^3 +ax+b) \\[3mm] \Bbb F_p[\xi,\eta]/(-\eta^2+\xi^3 +'a\xi+'b) &\longleftarrow &\Bbb F_p[x,y]/(-y^2+x^3 +ax+b) \\ (\ X(\xi,\eta),\ Y(\xi,\eta)\ )\ =\ (X,Y) &\longleftarrow &(x,y)\ . \end{array} $$ The elliptic curve $E$ is given in fact by projective coordinates, but I removed the point at infinity, wrote than "quickly" an affine version. Strictly speaking, $\xi,\eta$ may be rational, not only polynomial in $x,y$, so the quotient ring notation is not exact. The multiplication-by-two morphism on $E$, written at ring level involves denominators for instance. Just take the fraction field of the rings displayed above.

The arrows $\to$ are written in the category of varieties.

The arrows $\leftarrow$ are written in the category rings.

It is of course simpler to work with rings, so let us do that now.

(The same applies also for two different elliptic curves, having different equations.)

I tried to make distinction in the use of variables.

• It is important, that the functions $X=X(\xi,\eta)$, $Y=Y(\xi,\eta)$ involve (polynomials with) coefficients in the base field $K$.

• The map of rings above, determined by describing the images $X,Y$ of $x,y$, is a valid map, iff considering the polynomial (the rational expression) $$-Y^2(\xi,\eta) +X^3(\xi,\eta)+a(\xi,\eta)+b\ ,$$ the image of the generator of the ring in the R.H.S., and factorizing it in $\Bbb F_p[\xi,\eta]$, we get the factor $-\eta^2+\xi^3+a\xi+b$. (So ideal is mapped into ideal.)

• Back to $E\to E$, same elliptic curve. The situation becomes simpler:

$$ \begin{array}{rcl} E &\longrightarrow &E \\ \text{Spec } \Bbb F_p[x,y]/(-y^2+x^3 +ax+b) &\longrightarrow &\text{Spec } \Bbb F_p[x,y]/(-y^2+x^3 +ax+b) \\[3mm] \Bbb F_p[x,y]/(-y^2+x^3 +ax+b) &\longleftarrow &\Bbb F_p[x,y]/(-y^2+x^3 +ax+b) \\ (\ X(x,y),\ Y(x,y)\ )\ =\ (X,Y) &\longleftarrow &(x,y)\ . \end{array} $$ (It is only to make clear the last line, that I considered the $\xi,\eta$ variables in between, hope it is clear the possible confusion, and the rather didactical need to have an intermezzo with $\xi,\eta$.)

• The situation is even simpler now. Theorems insure that every such morphism is of the following shape for a suitable $u\in K$: $$ \begin{aligned} X &= u^2 x\ ,\\ Y &= u^3 y\ . \end{aligned} $$ Here, $u$ must satisfy: $$ \begin{aligned} a &= u^4 a\ ,\\ b &= u^6 b\ . \end{aligned} $$ See for instance J. Silverman, The Arithmetic Of Elliptic Curves, III.10, The Automorphism Group, Theorem 10.1 (2nd edition), page 103. So in case the characteristic is not $2,3$, we have the following choices for a $u$:

  • If $a,b\ne 0$, then $1=u^4=u^6$, so $u^2=1$, so $u=\pm 1$. For the two choices we get two automorphisms, the identity, $(x,y)\to (X,Y)=(x,y)$, and the times-minus-one morphism $(x,y)\to (X,Y)=(x,-y)$.

  • If $a=0$, $b\ne 0$, then the condition $a=u^4a$ is trivially fulfilled, so we need only $1=u^6$. For each such $u$ we have the map $(x,y)\to^u (X,Y)=(u^2x,u^3y)$. Indeed, the relation $-y^2+x^3+b$ is mapped to $-Y^2+X^3+b=-(u^3y)^2+(u^2x)^3+b=-u^6y^2+u^6x^3+b=-y^2+x^3+b$. So the relation(s) go/es to relation(s). This is our case.

  • If $a\ne 0$, $b=0$, then the condition $b=u^6b$ is trivially fulfilled, so we need only $1=u^4$. For each such $u$ we have the map $(x,y)\to^u (X,Y)=(u^2x,u^3y)$. Indeed, the relation $-y^2+x^3+ax$ is mapped to $-Y^2+X^3+aX=-(u^3y)^2+(u^2x)^3+a(u^2x)=u^2(-y^2+x^3+ax)$. We could factor $(-y^2+x^3+ax)$.

• We work now over a very special field, $\Bbb F_p$. Which are the $6$.th roots of unity in it? Sage code:

   sage: p = 2^256 - 4294968273
   sage: F = GF(p)
   sage: R.<x> = PolynomialRing(F)
   sage: (x^6-1).roots(multiplicities=False)
  
   [115792089237316195423570985008687907853269984665640564039457584007908834671662,
    60197513588986302554485582024885075108884032450952339817679072026166228089409,
    60197513588986302554485582024885075108884032450952339817679072026166228089408,
    55594575648329892869085402983802832744385952214688224221778511981742606582255,
    55594575648329892869085402983802832744385952214688224221778511981742606582254,
    1]
  

So $K=\Bbb F_p$, for $p= 2^{256}-4294968273$, contains all $6$.th order roots of unity. So all six automorphisms above are defined over $K$.

• As a notational issue, we have $\mu_6(K)$ of cardinality six.

---

Some few words about twists. The theory is well covered in text books, here only some examples.

We start with an elliptic curve having equation $$E=E_1\ :\ y^2 =\underbrace{x^3+ax+b}_{=f(x)}\ .$$ Let $E_d$ be the the curve defined by: $$E_d\ :\ dY^2=\underbrace{X^3+aX+b}_{=f(X)}\ .$$ It is clear that $x=X$, $y=Y\sqrt d$ defines an isomorphism of curves. But, $\sqrt d$ may not be in the field. We "identify" all isomorphic curves. For instance, $E=E_1$ is isomorphic with all curves $E_{d^2}$, $d\in K$, over $K$. For other choices of $d$, $d$ not a square in $K$, we do not get an isomorphic curve. Such a curve, in fact all its class of isomorphism is called a twist. The curves $E_1$ and $E_d$ become isomorphich if we enlarge the coefficients, passing to the quadratic extension $K(\sqrt d)$ over $K$. One can give a structure of a group for these twists, at least as a set, the considered $2$-twists can be identified with $K^\times$ modulo the group $(K^\times)^2$ of squares in it.

---

Our family of curves admit also an other kind of twist.

We start with

$$E=E_1\ :\ y^2 =x^3+b\ .$$ Let $E'_d$ be the the curve defined by: $$E'_d\ :\ Y^2=X^3+bd\ .$$ We extend the scalars, the field $K$, so that $S=\sqrt [6]d$ is adjoined. We divide in the equation of $E'_d$ by $d=S^6$, and set the correspondence: $x/S^2=X$, $y/S^3=Y$, it defines an isomorphism of curves. But, $\sqrt d$ may not be in the field. We "identify" all isomorphic curves. For instance, $E=E_1$ is isomorphic with all curves $E_{d^2}$, $d\in K$, over $K$.

Then for a given $d$ it makes sense to consider the twists:

• $E'_1=E_1\cong E'_{d^6}$,

• $E'_{d}$,

• $E'_{d^2}$,

• $E'_{d^3}\cong E_{d^3}$, this is a quadratic twist,

• $E'_{d^4}$,

• $E'_{d^5}$.

The reference gives all details.

---

Addendum:

I will try to use sage code (free software, which collects in one program all/most elliptic curve soft on the market), that exemplifies the above.

We will work over $F=\Bbb F_{19}$, since $F^\times$ has order $18$, divisible by $6$, so that $F^\times/(F^\times)^6$ is not trivial, thus nontrivial sextic twists of some given curve will exist. A multiplicative generator of $F^\times$ is

sage: F = GF(19)
sage: F.multiplicative_generator()
2

so the classes modulo $(F^\times)^6$ are:

sage: for k in [0..5]:
....:     for n in [0..2]:
....:         print F(2)^k * F(2)^(6*n),
....:     print
....:      
1 7 11
2 14 3
4 9 6
8 18 12
16 17 5
13 15 10

Let us initialize all twists of $E$, given by $y^2=x^3+1$, using ad-hoc code:

sage: C = [None] + [ EllipticCurve( F, [0,k] ) for k in [1..18] ]
sage: C
[None,
 Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 3 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 5 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 6 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 8 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 9 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 11 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 12 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 13 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 14 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 15 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 16 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 17 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 18 over Finite Field of size 19]
sage: C[1].is_isomorphic( C[11] )
True
sage: C[1].is_isomorphic( C[7] )
True
sage: C[1].is_isomorphic( C[8] )
False
sage: C[1].is_quadratic_twist( C[8] )
15
sage: C[1].is_quadratic_twist( C[9] )
0
sage: C[1].is_sextic_twist( C[9] )
9

A None was inserted on the zeroth position of the list C of elliptic curves, so that the places correspond to the $a_6$--coefficients. Then there were some tests. In the list of $6$.th powers we have the numbers $1,7,11$. (Taken mod $19$.) A first check was to see if indeed $C_1\cong C_{11}$, yes, this was the case. Then we have checked, if passing from $a_6=1$ to $a_6=2^3\cdot 1$, i.e. multiplying by a third power, produces a quadratic twist. Yes, this is the case.

I had to edit the post, after the following checks:

sage: C[2].is_isomorphic( C[4] )
False
sage: C[2].is_isomorphic( C[8] )
False
sage: C[2].is_isomorphic( C[16] )
False
sage: C[2].is_isomorphic( C[13] )
False
sage: C[2].is_isomorphic( C[14] )
True
sage: C[2].is_isomorphic( C[3] )
True

(The sextic twist with $2$ is not isomorphic with the sextic twist with $2^5$, I had a bad bag on the h(ea)d.)

The situation with $p=19$, so that $p-1$ is divisible by $6$, is similar to the situation for the $p$ in the post,

sage: factor( 2^256 - 4294968273 - 1 )
2 * 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371

since in thiscase $p-1$ is aslo divisible by $6$.

There are $6$ different, non-isomorphic twists, that can be obtained by using the powers $0,1,2,3,4,5$ of the multiplicative generator:

sage: p = 2^256 - 4294968273
sage: F = GF(p)
sage: F.multiplicative_generator()
3