# Elliptic Curve Twist

Hello, I am trying to compute the quadratic twist for an example of an Elliptic curve defined over a GF(p^8) Field: With

p=3351951982486667453837338848452726606028033606935065896469552348842908133596080151967071453287452469772970937967942438575522391344438242727636910570385409

and an Elliptic curve defined as:

E = ElllipticCurve(GF(p),[1,0])


given the extensions:

F2.<i> = GF(p^2, modulus=x^2 + 11)
F4.<j> = GF(p^4, modulus=x^4 + 11)
F8.<k> = GF(p^8, modulus=x^8 + 11)


I am trying to compute a twist of the elliptic curve defined over F8, of the twist equation form: y^2=x^3+a w^4 x, while a=1, and w satisfies the following: $w\in F_{p^8}$ and $w^4 \in F_{p^2}$, $w^2 \in F_{p^4}$ and $w^3 \in F_{p^{8}} \setminus F_{p^{4}}$

Is there any sage command that would help with this problem ?

Another way but I didn't know how to write it in sage: {1,w,w^2,w^3} are the basis of $F_{p^8}$ as a vector space over $F_{p^{2}}$.

edit retag close merge delete

Sort by » oldest newest most voted

To solve the problem you state first:

sage: E=EllipticCurve(GF(p),[1,0])
sage: Ek=E.base_extend(F8)

more

Should it not the resulted Elliptic Curve be defined over $F_{p^{2}}$ instead of $F_{p^{8}}$

( 2019-02-22 06:57:41 -0500 )edit

If $E$ and $E'$ are elliptic curves over $\mathbb{F}_q$ that are non-isomorphic quadratic twists, then their base changes to $\mathbb{F}_{q^2}$ are isomorphic. There is a quadratic twist of your curve $E$ that can be defined over $\mathbb{F}_{p^2}$ (and you can compute it in exactly the same way), but when you base-change it to $\mathbb{F}_{p^4}$, it is isomorphic to $E$.

( 2019-02-22 11:37:13 -0500 )edit

I don't really understand the problems here. When you write E.quadratic_twist(d) you are defining an elliptic curve which is only defined up to isomorphism, and whose isomorphism class only depends on d modulo squares (assuming characteristic not 2 here). So twisting by d and d/4 give isomorphic curves. The code is written to work well with long as well as short Weierstrass equations.

more

The problem is maybe the "unexpected twist", when we want to control it. (For finite fields we can also let sage do the job without twisting parameter, but usually, i want to have the control on it.) If this is rather the question, here is some answer.

We start with an elliptic curve with $a_1=a_3=0$ over some field of characteristic $\ne 2,3$. Then this is the curve: $$E\ :\ y^2=x^3+a_2x^2+a_4x+a_6\ ,$$ and one associates $b_2=4a_2$, $b_4=2a_4$, $b_6=4a_6$, so that the equation is also: $$E\ :\ y^2=x^3+\frac{b_2}4x^2+\frac{b_4}2x+\frac{b_6}4\ .$$ Now we look in the implementation of the method quadratic_twist via E.quadratic_twist?? e.g. after the elliptic curve instance in the OP was done with success and see the lines:

    if char!=2:
b2,b4,b6,b8=self.b_invariants()
# E is isomorphic to  [0,b2,0,8*b4,16*b6]
return EllipticCurve(K,[0,b2*D,0,8*b4*D**2,16*b6*D**3])


where D is the "twisting parameter", since we want to control the twist.

Well, there is not too much spacing (and reference) in the code for my taste, but we can extract the information, that the following is the returned twist, using $b$-parameters in an $a$-parameter initialization:

$$E'\ :\ Y^2 = X^3 + 4D\; a_2X^2+(4D)^2\; a_4X+(4D)^3\; a_6\ .$$ This was many times unexpected for me. Now let us consider a special example in small fields, say $\Bbb F_p=$GF(409). In it, $7$ and $11$ are not squares. Then we may pass from $E:\ y^2=x^3+x$ to the twist $E_d:\ y^2=x^3+d^2x$, via

E.quadratic_twist( d/4 )


(with a "twist of the twisting parameter")

and for $d$ taking some small values we can write some testing sage code as follows:

sage: F = GF(409)
sage: E = EllipticCurve(F, [1,0])
sage: for d in [1..19]:
....:     print ( "d=%2s :: Square? %5s :: |Ed|=%s :: E ~ Ed? %s"
....:             % (d, F(d).is_square(), Ed.order(), E.is_isomorphic(Ed)) )
....:
d= 1 :: Square?  True :: |Ed|=416 :: E ~ Ed? True
d= 2 :: Square?  True :: |Ed|=416 :: E ~ Ed? True
d= 3 :: Square?  True :: |Ed|=416 :: E ~ Ed? True
d= 4 :: Square?  True :: |Ed|=416 :: E ~ Ed? True
d= 5 :: Square?  True :: |Ed|=416 :: E ~ Ed? True
d= 6 :: Square?  True :: |Ed|=416 :: E ~ Ed? True
d= 7 :: Square? False :: |Ed|=404 :: E ~ Ed? False
d= 8 :: Square?  True :: |Ed|=416 :: E ~ Ed? True
d= 9 :: Square?  True :: |Ed|=416 :: E ~ Ed? True
d=10 :: Square?  True :: |Ed|=416 :: E ~ Ed? True
d=11 :: Square? False :: |Ed|=404 :: E ~ Ed? False
d=12 :: Square?  True :: |Ed|=416 :: E ~ Ed? True
d=13 :: Square? False :: |Ed|=404 :: E ~ Ed? False
d=14 :: Square? False :: |Ed|=404 :: E ~ Ed? False
d=15 :: Square?  True :: |Ed|=416 :: E ~ Ed? True
d=16 :: Square?  True :: |Ed|=416 :: E ~ Ed? True
d=17 :: Square?  True :: |Ed|=416 :: E ~ Ed? True
d=18 :: Square?  True :: |Ed|=416 :: E ~ Ed? True
d=19 :: Square? False :: |Ed|=404 :: E ~ Ed? False
sage: Ed
Elliptic Curve defined by y^2 = x^3 + 361*x over Finite Field of size 409
sage: 19^2
361


The last curve in the loop was printed.

I often have this problem, and always look in the code, get that 8*b4*D**2 or 16*b6*D**3 in the position i expect something else, go to the formula for b4 and b6 in Ian Connell's book, write the $(4D)^2$, respectively $(4D)^3$ on a piece of paper, write my code with d/4 instead of d, and comment it also to have it done for the next time.

In your case now, things should work in the same way, the prints are but rather hard to trace back.

more