Twists of an Elliptic Curve over a Finite Field (secp256k1)

dan_fulea
5650 ●5 ●44 ●97

In 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".

link

add a comment

Twists of an Elliptic Curve over a Finite Field (secp256k1)

1 Answer

Your Answer

Question Tools

Stats

Related questions

Twists of an Elliptic Curve over a Finite Field (secp256k1) savecancel

1 Answer

Your Answer

Question Tools

Stats

Related questions

Twists of an Elliptic Curve over a Finite Field (secp256k1)