# elliptic curve over extension field

This post is a wiki. Anyone with karma >750 is welcome to improve it.

how to define elliptic curve over extension field GF(2^113) in sagemath

the equation is y^2+xy=x^3+ax^2+b over F2^m

where

a=984342157317881800509153672175863 b=4720643197658441292834747278018339

edit retag close merge delete

Please tell us how to see the two "cryptic" numbers a, b as elements of the above field. Everything else remained is simple, just use EllipticCurve( F, [ 1, 0, 0, a, b] ) after defining the field F.

For example, over GF(11):

sage: F = GF( 11 )
sage: E = EllipticCurve( F, [ 1,2,3,4,9 ] )
sage: E
Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 9 over Finite Field of size 11

( 2017-11-17 11:12:57 +0200 )edit

To interpret a and b as elements of K = GF(2^113), you probably want to use K.fetch_int(a). See the documentation

( 2017-11-17 13:13:43 +0200 )edit

Sorry, take one more look here, and saw incidentally, that $a$ comes with $x^2$ in $$y^2 +xy = x^3 + a x^2 + b\ ,$$ so the needed command is:

EllipticCurve( F, [ 1, a, 0, 0, b ] )


for instance, over some other field:

sage: a, b, F = 10, 11, QQ; E = EllipticCurve( F, [ 1, a, 0, 0, b ] ); E
Elliptic Curve defined by y^2 + x*y = x^3 + 10*x^2 + 11 over Rational Field

( 2017-11-18 21:01:54 +0200 )edit

Sort by » oldest newest most voted

There is still some needed input to get the "right curve". So let me "guess" (or rather search the net for) it...

Let us consider first the section 3.2.1 in

http://www.secg.org/SEC2-Ver-1.0.pdf

because the book Song Y. Yan, Quantum Computing for Elliptic Curve Discrete Logarithms, (page 187) is not freely accessible.

This is related to the question, so let us write code, which reconstructs the situation.

The field with $2^{113}$ elements is modelled as $K = \mathbb F_2[X]\ /\ (X^{113}+X^9+1)$ . In sage one has to declare X^113 + X^9 + 1 as the modulus. Code:

R.<X> = PolynomialRing( GF(2) )
K.<x> = GF( 2**113, modulus = X^113 + X^9 + 1 )


This defines inside sage first the field $K$:

sage: K
Finite Field in x of size 2^113
sage: x.minpoly()
x^113 + x^9 + 1


The numbers a, b posted have the hex-representation from the article.

a = 984342157317881800509153672175863
b = 4720643197658441292834747278018339

print "hex(a) =", hex(a)
print "hex(b) =", hex(b)


This gives:

hex(a) = 3088250ca6e7c7fe649ce85820f7
hex(b) = e8bee4d3e2260744188be0e9c723


so the numbers $a,b$ from the two sources, and from the posted question coincide. (But in the post, the essential information, the modulus, was missing.)

So let us put all together, with the data from the book Quantum Computing...:

R.<X> = PolynomialRing( GF(2) )
K.<x> = GF( 2**113, modulus = X^113 + X^9 + 1 )

a = 984342157317881800509153672175863
b = 4720643197658441292834747278018339

A = K.fetch_int( a )
B = K.fetch_int( b )

E = EllipticCurve( K, [ 1, A, 0, 0, B ] )

P = E.point( ( K.fetch_int( 8611161909599329818310188302308875 ) ,
K.fetch_int( 7062592440118670058899979569784381 ) , ) )

Q = E.point( ( K.fetch_int( 6484392715773238573436200651832265 ) ,
K.fetch_int( 7466851312800339937981984969376306 ) , ) )

k = 2760361941865110448921065488991383

print "Is Q = k*P in E(K)? %s" % ( Q == k*P )


And we get:

Is Q = k*P in E(K)? True

more