# computing order of elliptic curves over binary field

Do you have any information on how to compute order of elliptic curves over binary field in SAGE mathematics software? Example: I have the following domain parameters which are taken from

p = 0800000000000000000000000000000000000000C9
a = 07B6882CAAEFA84F9554FF8428BD88E246D2782AE2
b = 0713612DCDDCB40AAB946BDA29CA91F73AF958AFD9
x = 0369979697AB43897789566789567F787A7876A654
y = 00435EDB42EFAFB2989D51FEFCE3C80988F41FF883


The problem I am facing is to to know the order of this elliptic curve? I ahve got on the net that it is possible to compute using this library sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari and it takes these parameters properly with out any error. But there is error while requesting the order of that parameter.

This was what I deed in sage:

FF = sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari;
order = 2**163;
c = 07B6882CAAEFA84F9554FF8428BD88E246D2782AE2;
b = 0713612DCDDCB40AAB946BDA29CA91F73AF958AFD9
K.<x>= GF(2)[];
K.<k> = FF(order, 'a', modulus = x^163 + x^7 + x^6 + x^3 + 1)[];
K163_curve = EllipticCurve(K,[1,c,0,0,b]);K163_curve

edit retag close merge delete

Our free book http://software.intel.com/en-us/articles/ipp-crypto-guide/ pages 264,265 contains some computations in C/C++ with "your" curve, including the order. We were not able to compute the order in Sage

( 2012-04-25 19:14:26 -0500 )edit

Sort by » oldest newest most voted

The order of the curve is: $$2\cdot 5846006549323611672814738465098798981304420411291\ .$$ (The second factor is a prime.) Source:

Intel(R) Integrated Performance Primitives, Cryptography Guide, IPP 7.1, Andrzej Chrzeszczyk, Jakub Chrzeszczyk, September, 2012, page 214.

https://software.intel.com/sites/default/files/article/181895/intelcrypt710.pdf

(One has to read between the lines.)

The above source / link in the comments is no longer available.

Sage could in my hands with the present libraries not proceed with the search. (It was even hard to kill the sage process, no chance to access mouse and keyboard after some minutes. It took all resources on the machine.)

Here is the code that only verifies the order.

P  = 0x0800000000000000000000000000000000000000C9
c  = 0x07B6882CAAEFA84F9554FF8428BD88E246D2782AE2
b  = 0x0713612DCDDCB40AAB946BDA29CA91F73AF958AFD9
x0 = 0x0369979697AB43897789566789567F787A7876A654
y0 = 0x00435EDB42EFAFB2989D51FEFCE3C80988F41FF883

R.<X> = PolynomialRing( GF(2) )
modulus = R( P.digits(2) )

q = 2 ** 163
F = GF( q, modulus=modulus, name='x' )
E = EllipticCurve( F, [ 1, F(c.digits(2)), 0, 0, F(b.digits(2)) ] )

POINT = E.point( ( F(x0.digits(2)), F(y0.digits(2)) ) )
PRIME = 5846006549323611672814738465098798981304420411291

print "Is   PRIME * POINT == 0? %s" % ( (   PRIME * POINT ).is_zero() )
print "Is 2*PRIME * POINT == 0? %s" % ( ( 2*PRIME * POINT ).is_zero() )

print "The value 2*PRIME is in hex between the Hasse bounds as follows:"
print "%s :: hex of ceil  of q + 1 - 2 sqrt(q)" % hex(  ceil( q + 1 - 2*sqrt(q) ) )
print "%s :: hex of 2*PRIME = order of ( E( GF(q) ), + )" % hex( 2*PRIME )
print "%s :: hex of floor of q + 1 + 2 sqrt(q)" % hex( floor( q + 1 + 2*sqrt(q) ) )


And we get:

Is   PRIME * POINT == 0? True
Is 2*PRIME * POINT == 0? True
The value 2*PRIME is in hex between the Hasse bounds as follows:
7fffffffffffffffffffa57d86660310cdbdd3415 :: hex of ceil  of q + 1 - 2 sqrt(q)
7fffffffffffffffffffe91556d1385394e204f36 :: hex of 2*PRIME = order of ( E( GF(q) ), + )
800000000000000000005a827999fcef32422cbed :: hex of floor of q + 1 + 2 sqrt(q)

more