Ask Your Question
1

Elliptic Curve Twist

asked 2019-02-21 10:03:56 -0500

Joseph gravatar image

updated 2019-02-22 11:48:18 -0500

FrédéricC gravatar image

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}}$.

Thanks in advance.

edit retag flag offensive close merge delete

2 answers

Sort by » oldest newest most voted
1

answered 2019-02-22 02:16:15 -0500

nbruin gravatar image

To solve the problem you state first:

sage: E=EllipticCurve(GF(p),[1,0])
sage: Ek=E.base_extend(F8)
sage: Ek.quadratic_twist()
edit flag offensive delete link more

Comments

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

Joseph gravatar imageJoseph ( 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$.

nbruin gravatar imagenbruin ( 2019-02-22 11:37:13 -0500 )edit
0

answered 2019-02-25 13:33:52 -0500

dan_fulea gravatar image

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]:
....:     Ed = E.quadratic_twist(d/4)
....:     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.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2019-02-21 10:03:56 -0500

Seen: 94 times

Last updated: Feb 25