Ask Your Question
0

elliptic curve over extension field

asked 2017-11-17 02:46:10 -0600

this post is marked as community wiki

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 flag offensive close merge delete

Comments

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
dan_fulea gravatar imagedan_fulea ( 2017-11-17 04:12:57 -0600 )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

B r u n o gravatar imageB r u n o ( 2017-11-17 06:13:43 -0600 )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
dan_fulea gravatar imagedan_fulea ( 2017-11-18 14:01:54 -0600 )edit

1 answer

Sort by ยป oldest newest most voted
0

answered 2017-11-18 16:04:21 -0600

dan_fulea gravatar image

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
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-11-17 02:46:10 -0600

Seen: 66 times

Last updated: Nov 18