ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 17 Nov 2017 13:47:06 +0100How to defining a twist on an elliptic curvehttps://ask.sagemath.org/question/39597/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)Thu, 16 Nov 2017 11:43:57 +0100https://ask.sagemath.org/question/39597/how-to-defining-a-twist-on-an-elliptic-curve/Answer by dan_fulea for <p>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:</p>
<p>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. </p>
<h1>MWE</h1>
<h2>Mathematical definition:</h2>
<p>$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)$.</p>
<h2>Define the fields and curves</h2>
<pre><code>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])
</code></pre>
<h2>Defining the point and pre-computations</h2>
<pre><code>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
</code></pre>
<h2>The not working twist</h2>
<pre><code>#twist
E4( (Q16[0]*b^2, Q16[1]*b^3))
</code></pre>
<p>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 </p>
<pre><code>E4.quartic_twist(v^-1)
</code></pre>
https://ask.sagemath.org/question/39597/how-to-defining-a-twist-on-an-elliptic-curve/?answer=39614#post-id-39614I 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])
Thu, 16 Nov 2017 22:25:13 +0100https://ask.sagemath.org/question/39597/how-to-defining-a-twist-on-an-elliptic-curve/?answer=39614#post-id-39614Comment by Shalec for <p>I think the following is needed, notations slightly changed, but in the same spirit:</p>
<pre><code>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 ) )
</code></pre>
<p>Results:</p>
<pre><code>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)
</code></pre>
<p>The <code>for</code> 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 <code>c_invariants</code> twist for <code>c4</code>, as in the following lines delivered by <code>E.quartic_twist??</code></p>
<pre><code> 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])
</code></pre>
https://ask.sagemath.org/question/39597/how-to-defining-a-twist-on-an-elliptic-curve/?comment=39641#post-id-39641Wow 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$.Fri, 17 Nov 2017 13:47:06 +0100https://ask.sagemath.org/question/39597/how-to-defining-a-twist-on-an-elliptic-curve/?comment=39641#post-id-39641