elliptic curve over extension field

savecancel

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