computing order of elliptic curves over binary field

asked 2012-04-24 11:15:06 +0200

twoforone
31 ●2 ●3 ●6

updated 2015-01-18 11:26:06 +0200

FrédéricC

5125 ●3 ●43 ●111

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

Comments

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

achrzesz ( 2012-04-26 02:14:26 +0200 )edit

add a comment

answered 2017-03-25 19:06:33 +0200

dan_fulea
5337 ●5 ●43 ●90

updated 2017-03-25 19:13:00 +0200

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)

edit flag offensive delete link

add a comment

Your Answer

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

computing order of elliptic curves over binary field

Comments

1 Answer

Your Answer

Question Tools

Stats

Related questions

computing order of elliptic curves over binary field edit

Comments

1 Answer

Your Answer

Question Tools

Stats

Related questions

computing order of elliptic curves over binary field