ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 22 May 2018 12:14:22 -0500Twists of an Elliptic Curve over a Finite Field (secp256k1)http://ask.sagemath.org/question/42306/twists-of-an-elliptic-curve-over-a-finite-field-secp256k1/ I would like to calculate the twists of secp256k1 up to isomorphism (find one representative for the quadratic twist, and so on). Therefore I tried the function <br/>
E.quadratic_twist(d) and E.sextic_twist(d) <br/>
with E = EllipticCurve(GF(115792089237316195423570985008687907853269984665640564039457584007908834671663), [0,0,0,0,7]).
<br/>
The problem is that I don't understand what the variable $d$ does in this function. <br/>
I tried different $d$ and found a quadratic twist with $d=3$ $E' : y^2 = x^3 + 12096 = x^3 + 7 \cdot (12)^3$ and tested that $12$ is square-free in $\mathbb{F}_q$, and two sextic twists with $d=3,7$: $E^{d_6}_1: y^2 = x^3 + 7\cdot 139968$ and $E^{d_6}_2: y^2 = x^3 + 7\cdot 326592$ with $139968$ and $326592$ square- and cube-free in $\mathbb{F}_q$. <br/>
<br/>
But my method is rather brute-force, since I don't really understand the function, and I am also not sure how many different sextic twists sexp256k1 has (up to isomorphism). I think it is two, but I am not sure. <br/>
<br/>
My next question is, if there is a way to calculate the cubic twist with a similar function?
Thu, 10 May 2018 09:55:45 -0500http://ask.sagemath.org/question/42306/twists-of-an-elliptic-curve-over-a-finite-field-secp256k1/Answer by dan_fulea for <p>I would like to calculate the twists of secp256k1 up to isomorphism (find one representative for the quadratic twist, and so on). Therefore I tried the function <br>
E.quadratic_twist(d) and E.sextic_twist(d) <br>
with E = EllipticCurve(GF(115792089237316195423570985008687907853269984665640564039457584007908834671663), [0,0,0,0,7]).
<br>
The problem is that I don't understand what the variable $d$ does in this function. <br>
I tried different $d$ and found a quadratic twist with $d=3$ $E' : y^2 = x^3 + 12096 = x^3 + 7 \cdot (12)^3$ and tested that $12$ is square-free in $\mathbb{F}_q$, and two sextic twists with $d=3,7$: $E^{d_6}_1: y^2 = x^3 + 7\cdot 139968$ and $E^{d_6}_2: y^2 = x^3 + 7\cdot 326592$ with $139968$ and $326592$ square- and cube-free in $\mathbb{F}_q$. <br>
<br>
But my method is rather brute-force, since I don't really understand the function, and I am also not sure how many different sextic twists sexp256k1 has (up to isomorphism). I think it is two, but I am not sure. <br>
<br>
My next question is, if there is a way to calculate the cubic twist with a similar function?</p>
http://ask.sagemath.org/question/42306/twists-of-an-elliptic-curve-over-a-finite-field-secp256k1/?answer=42393#post-id-42393In order to get the implemented algorithm for a specific method, it is always a good idea to instantiate some object with the corresponding method, then to ask in the ipython sage interpreter what it is, and/or which code does it work behind. In our case, using a simpler field, $19$ elements only, i did first the following:
F = GF(13)
E = EllipticCurve( F, [0,1] )
D = F(2)
E.sextic_twist?
Then, by the last line, we obtain the usual doc string of the method, in this case:
sage: F = GF(13)
....: E = EllipticCurve( F, [0,1] )
....: D = F(2)
....: E.sextic_twist?
....:
Signature: E.sextic_twist(D)
Docstring:
Return the quartic twist of this curve by D.
INPUT:
* "D" (must be nonzero) -- the twisting parameter..
Note: The characteristic must not be 2 or 3, and the j-invariant
must be 0.
EXAMPLES:
sage: E=EllipticCurve_from_j(GF(13)(0)); E
Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 13
sage: E1=E.sextic_twist(2); E1
Elliptic Curve defined by y^2 = x^3 + 11 over Finite Field of size 13
sage: E.is_isomorphic(E1)
False
sage: E.is_isomorphic(E1,GF(13^2,'a'))
False
sage: E.is_isomorphic(E1,GF(13^4,'a'))
False
sage: E.is_isomorphic(E1,GF(13^6,'a'))
True
Init docstring: x.__init__(...) initializes x; see help(type(x)) for signature
File: /usr/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_field.py
Type: instancemethod
sage:
Of course, already in this example there are some questions about the way it works, i was alo expecting to pass from `E` to "an `E1`", which has a $2$, not the $11$ as free coefficient, so why do we get $y^2=x^3 +11$ as the $2$--twist?
For this i wanted to see also the code computing the story. This is obtained by asking for
sage: E.sextic_twist??
instead of `sage: E.sextic_twist?`, and it delivers in our case, after the doc string part:
K=self.base_ring()
char=K.characteristic()
D=K(D)
if char==2 or char==3:
raise ValueError("Sextic twist not defined in chars 2,3")
if self.j_invariant() !=K(0):
raise ValueError("Sextic twist not defined when j!=0")
if D.is_zero():
raise ValueError("Sextic twist requires a nonzero argument")
c4,c6=self.c_invariants()
# E is isomorphic to [0,0,0,0,-54*c6]
assert c4==0
return EllipticCurve(K,[0,0,0,0,-54*c6*D])
File: /usr/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_field.py
Type: instancemethod
(END)
Oh, so the way it works is as follows. We start with the elliptic curve given by
$$
y^2 = x^3+1\ ,\qquad\text{ over }\Bbb F_{13}\ .
$$
Now the code computes its $$c_4,\ c_6$$ invariants! There are formulas for the passage from the $a$'s, to the $b$'s, then to the $c$'c, in our case we pass as follows ...
sage: E
Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 13
sage: E.a_invariants()
(0, 0, 0, 0, 1)
sage: E.b_invariants()
(0, 0, 4, 0)
sage: E.c_invariants()
(0, 7)
The formulas are as folllows. We start with $a$-invariants, so that only $a_6\ne 0$, all other invariants are zero.
Then we compute $b_2,b_4,b_6,b_8$, for us is interesting only
$$b_6=4a_6\ .$$
Then we associate
$$c_6=-216b_6=-216\dot 4\cdot a_6=-864a_6\ .$$
And indeed:
sage: -864*F(1)
7
We consider now our "twist" (multiplication) of $c_6=7$ with $2$,
this is $14=-1$ (in $\Bbb F_{13}$) and the code is then passing to the curve
$$y^2 = x^3 - 54\cdot c_6\cdot D\ .$$
Alias
$$y^2 = x^3 + a_6\cdot D\cdot 6^6\ .$$
We get an equivalent twist, since
sage: 4*(-216)*(-54)
46656
sage: _.factor()
2^6 * 3^6
is a sixtth power, the sixth power of $6$, so the twisted number $D$ is "twisted itself", leading to an other isomorphic curve.
Finally, let us compare the implemented method with the obvious ad-hoc method implementing the twist:
F = GF(19)
G = F.unit_group()
print "F = %s" % F
print "G = units(F) has as elements those from the list\n%s" % str( G.list() )
print "G^6 has as elements...\n%s" % str( Set( [ g^6 for g in G.list() ] ) )
E = EllipticCurve( F, [0,1] )
print "Let E be the curve: %s" % E
for k in F:
if k == F(0):
continue
E1 = E.sextic_twist( k )
E2 = E.sextic_twist( k/6^6 )
E3 = EllipticCurve( F, [0,k] )
print "k = %s" % k
print "E1 = E.sextic_twist( %s ) = %s" % ( k, E1 )
print "E2 = E.sextic_twist( %s/6^6 ) = %s" % ( k, E2 )
print "E3 = EllipticCurve( F, [0,%s] ) = %s" % ( k, E3 )
print "Is E1 ~ E2? %s" % bool( E1.is_isomorphic( E2 ) )
print "Is E2 = E3? %s" % bool( E2 == E3 )
print
And the results are:
F = Finite Field of size 19
G = units(F) has as elements those from the list
(1, f, f^2, f^3, f^4, f^5, f^6, f^7, f^8, f^9, f^10, f^11, f^12, f^13, f^14, f^15, f^16, f^17)
G^6 has as elements...
{f^6, f^12, 1}
Let E be the curve: Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 19
k = 1
E1 = E.sextic_twist( 1 ) = Elliptic Curve defined by y^2 = x^3 + 11 over Finite Field of size 19
E2 = E.sextic_twist( 1/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 19
E3 = EllipticCurve( F, [0,1] ) = Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 2
E1 = E.sextic_twist( 2 ) = Elliptic Curve defined by y^2 = x^3 + 3 over Finite Field of size 19
E2 = E.sextic_twist( 2/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field of size 19
E3 = EllipticCurve( F, [0,2] ) = Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 3
E1 = E.sextic_twist( 3 ) = Elliptic Curve defined by y^2 = x^3 + 14 over Finite Field of size 19
E2 = E.sextic_twist( 3/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 3 over Finite Field of size 19
E3 = EllipticCurve( F, [0,3] ) = Elliptic Curve defined by y^2 = x^3 + 3 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 4
E1 = E.sextic_twist( 4 ) = Elliptic Curve defined by y^2 = x^3 + 6 over Finite Field of size 19
E2 = E.sextic_twist( 4/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 19
E3 = EllipticCurve( F, [0,4] ) = Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 5
E1 = E.sextic_twist( 5 ) = Elliptic Curve defined by y^2 = x^3 + 17 over Finite Field of size 19
E2 = E.sextic_twist( 5/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 5 over Finite Field of size 19
E3 = EllipticCurve( F, [0,5] ) = Elliptic Curve defined by y^2 = x^3 + 5 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 6
E1 = E.sextic_twist( 6 ) = Elliptic Curve defined by y^2 = x^3 + 9 over Finite Field of size 19
E2 = E.sextic_twist( 6/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 6 over Finite Field of size 19
E3 = EllipticCurve( F, [0,6] ) = Elliptic Curve defined by y^2 = x^3 + 6 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 7
E1 = E.sextic_twist( 7 ) = Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 19
E2 = E.sextic_twist( 7/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 19
E3 = EllipticCurve( F, [0,7] ) = Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 8
E1 = E.sextic_twist( 8 ) = Elliptic Curve defined by y^2 = x^3 + 12 over Finite Field of size 19
E2 = E.sextic_twist( 8/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 8 over Finite Field of size 19
E3 = EllipticCurve( F, [0,8] ) = Elliptic Curve defined by y^2 = x^3 + 8 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 9
E1 = E.sextic_twist( 9 ) = Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 19
E2 = E.sextic_twist( 9/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 9 over Finite Field of size 19
E3 = EllipticCurve( F, [0,9] ) = Elliptic Curve defined by y^2 = x^3 + 9 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 10
E1 = E.sextic_twist( 10 ) = Elliptic Curve defined by y^2 = x^3 + 15 over Finite Field of size 19
E2 = E.sextic_twist( 10/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field of size 19
E3 = EllipticCurve( F, [0,10] ) = Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 11
E1 = E.sextic_twist( 11 ) = Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 19
E2 = E.sextic_twist( 11/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 11 over Finite Field of size 19
E3 = EllipticCurve( F, [0,11] ) = Elliptic Curve defined by y^2 = x^3 + 11 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 12
E1 = E.sextic_twist( 12 ) = Elliptic Curve defined by y^2 = x^3 + 18 over Finite Field of size 19
E2 = E.sextic_twist( 12/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 12 over Finite Field of size 19
E3 = EllipticCurve( F, [0,12] ) = Elliptic Curve defined by y^2 = x^3 + 12 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 13
E1 = E.sextic_twist( 13 ) = Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field of size 19
E2 = E.sextic_twist( 13/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 13 over Finite Field of size 19
E3 = EllipticCurve( F, [0,13] ) = Elliptic Curve defined by y^2 = x^3 + 13 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 14
E1 = E.sextic_twist( 14 ) = Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field of size 19
E2 = E.sextic_twist( 14/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 14 over Finite Field of size 19
E3 = EllipticCurve( F, [0,14] ) = Elliptic Curve defined by y^2 = x^3 + 14 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 15
E1 = E.sextic_twist( 15 ) = Elliptic Curve defined by y^2 = x^3 + 13 over Finite Field of size 19
E2 = E.sextic_twist( 15/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 15 over Finite Field of size 19
E3 = EllipticCurve( F, [0,15] ) = Elliptic Curve defined by y^2 = x^3 + 15 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 16
E1 = E.sextic_twist( 16 ) = Elliptic Curve defined by y^2 = x^3 + 5 over Finite Field of size 19
E2 = E.sextic_twist( 16/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 16 over Finite Field of size 19
E3 = EllipticCurve( F, [0,16] ) = Elliptic Curve defined by y^2 = x^3 + 16 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 17
E1 = E.sextic_twist( 17 ) = Elliptic Curve defined by y^2 = x^3 + 16 over Finite Field of size 19
E2 = E.sextic_twist( 17/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 17 over Finite Field of size 19
E3 = EllipticCurve( F, [0,17] ) = Elliptic Curve defined by y^2 = x^3 + 17 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
k = 18
E1 = E.sextic_twist( 18 ) = Elliptic Curve defined by y^2 = x^3 + 8 over Finite Field of size 19
E2 = E.sextic_twist( 18/6^6 ) = Elliptic Curve defined by y^2 = x^3 + 18 over Finite Field of size 19
E3 = EllipticCurve( F, [0,18] ) = Elliptic Curve defined by y^2 = x^3 + 18 over Finite Field of size 19
Is E1 ~ E2? True
Is E2 = E3? True
I hope this explains the "twisted behavior" of the `sextic_twist".
Tue, 22 May 2018 12:14:22 -0500http://ask.sagemath.org/question/42306/twists-of-an-elliptic-curve-over-a-finite-field-secp256k1/?answer=42393#post-id-42393