How to defining a twist on an elliptic curve

Hey, I would like to do map points of the ellitptic curve $E(\mathbb F_{p^{k}})$ to its twist. I am able to define the twist on a mathematical way, but it returns always errors. I will give you a M(n)WE:

Aim: Get a generator of a r-torsion subgroup of E, lift that to E16 and twist it down to E4, to get a r-torsion subgroup-generator of E4.

MWE

Mathematical definition:

$E(\mathbb F_{p^{16}}): y^2=x^3+x$ and its quartic twist $E'(\mathbb F_{p^4}): y^2=x^3+2^{-1/4}x$. The point mapping is defined as $\psi: E\to E', (x,y,z)\mapsto (2^{-1/2}x, 2^{-3/4}y, z)$.

Define the fields and curves

p= 13
r=5
R=GF(p)
_.<x> = PolynomialRing(R)
R4.<x> = R.extension(x^4 - 2, 'x')
_.<y> = PolynomialRing(R)
R16.<y> = R.extension(y^16 -2, 'y')
_.<z> = PolynomialRing(R4)
R16_over_R4.<z> = R4.extension(z^4-x, 'z')

E = EllipticCurve(R, [1,0]) # y^2 = x^3+x
E4 = EllipticCurve(R4, [x,0])
E16 = EllipticCurve(R16, [1,0])


Defining the point and pre-computations

k= ZZ(E.order()/r) # since E.order()*P = (0:1:0), we can trick with that
b=R16(2^(-1)); b= sqrt(sqrt(2)) #the twisting parameter, that is a square in R4 and R16
P= E.gens()[0]
Q=k*P # check if Q != E((0,1,0)), if yes its a r-torsion point.
Q16 = E16(Q) #raise Q


The not working twist

#twist
E4( (Q16[0]*b^2, Q16[1]*b^3))


Sage is able to compute the quartic twist of its own, but I do not recieve the right twist, that I had computed by hand ( $E'$ ). Using

E4.quartic_twist(v^-1)

edit retag close merge delete

Sort by » oldest newest most voted

I think the following is needed, notations slightly changed, but in the same spirit:

p = 13
r = 5

F1 = GF(p)
R1.<X> = F1[]

F4.<c> = GF( p** 4 , modulus = X^4  - 2 )
R4.<Y> = F4[]

F16.<v> = F4.extension( X^4 - c )

b = 1/c
print "2b^4 = %s" % ( 2*b^4 )
print "v^4  = %s" % (   v^4 )

E1  = EllipticCurve( F1, [1,0] )
E4  = EllipticCurve( F4, [1,0] )    # E1.change_ring( F4 )
EE4 = EllipticCurve( F4, [c,0] )    # the twist
D   = E4.is_quartic_twist( EE4 )

# print E4 == E1.change_ring( F4 )

print "E4.is_quartic_twist( EE4 ) --> use %s" % D

# Possible twists with conjugates of c
for d in ( X^4-2 ).roots( ring=F, multiplicities=False ):
print "Twisting with d = %s" % d
Tw = E.quartic_twist( d )
print Tw
if EE.is_isomorphic( Tw ):
print "--> isomorphic to EE"
if E.is_isomorphic( Tw ):
print "--> isomorphic to E"
print

# Find the "exact value" for the twisting element
d = None
for u in F1:
if not u:
continue
Eu4 = E4.quartic_twist( u*c )
if Eu4 == EE4:
d = u*c
print "More exactly: Use quartic twist via d = %s" % ( u*c )

print
P = E1.gens()[0]
Q = k*P
Qx, Qy = Q.xy()
print "Consider the point Q = ", Q
print "E4( Q ) =", E4( Q )

E16  =  E4.change_ring( F16 )
EE16 = EE4.change_ring( F16 )

print "EE16.point( ( Qx * v^2, Qy * v^3 ) ) =", EE16.point( ( Qx * v^2, Qy * v^3 ) )


Results:

2b^4 = 1
v^4  = c
E4.is_quartic_twist( EE4 ) --> use c
Twisting with d = 12*c
Elliptic Curve defined by y^2 = x^3 + 4*c*x over Finite Field in c of size 13^4
--> isomorphic to EE

Twisting with d = 8*c
Elliptic Curve defined by y^2 = x^3 + 7*c*x over Finite Field in c of size 13^4
--> isomorphic to EE

Twisting with d = 5*c
Elliptic Curve defined by y^2 = x^3 + 6*c*x over Finite Field in c of size 13^4
--> isomorphic to EE

Twisting with d = c
Elliptic Curve defined by y^2 = x^3 + 9*c*x over Finite Field in c of size 13^4
--> isomorphic to EE

More exactly: Use quartic twist via d = 3*c

Consider the point Q =  (9 : 7 : 1)
E4( Q ) = (9 : 7 : 1)
EE16.point( ( Qx * v^2, Qy * v^3 ) ) = (9*v^2 : 7*v^3 : 1)


The for loop done w.r.t. roots of two is not relevant for the question, but may support the answer. Note that the twist is done programatically using the c_invariants twist for c4, as in the following lines delivered by E.quartic_twist??

        c4,c6=self.c_invariants()
# E is isomorphic to  [0,0,0,-27*c4,0]
assert c6==0
return EllipticCurve(K,[0,0,0,-27*c4*D,0])

more

Wow nice, thank you. Yesterday, after some hours of wondering, why this does not work or even produces different results, as I thought to get, I saw, that I missunderstood twists. They are becoming isomorphic over the extension field, not through the different fields ($F_k:=\mathbb F_{p^k}$) $F_4$ and $F_{16}$. So the r-torsion point I found worked over $F_{16}$, but now over $F_4$.

( 2017-11-17 06:47:06 -0500 )edit