ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 25 Mar 2017 19:06:33 +0100computing order of elliptic curves over binary fieldhttps://ask.sagemath.org/question/8919/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
Tue, 24 Apr 2012 11:15:06 +0200https://ask.sagemath.org/question/8919/computing-order-of-elliptic-curves-over-binary-field/Comment by achrzesz for <p>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>
<pre><code>p = 0800000000000000000000000000000000000000C9
a = 07B6882CAAEFA84F9554FF8428BD88E246D2782AE2
b = 0713612DCDDCB40AAB946BDA29CA91F73AF958AFD9
x = 0369979697AB43897789566789567F787A7876A654
y = 00435EDB42EFAFB2989D51FEFCE3C80988F41FF883
</code></pre>
<p>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.</p>
<p>This was what I deed in sage:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/8919/computing-order-of-elliptic-curves-over-binary-field/?comment=19862#post-id-19862Our 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 SageThu, 26 Apr 2012 02:14:26 +0200https://ask.sagemath.org/question/8919/computing-order-of-elliptic-curves-over-binary-field/?comment=19862#post-id-19862Answer by dan_fulea for <p>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>
<pre><code>p = 0800000000000000000000000000000000000000C9
a = 07B6882CAAEFA84F9554FF8428BD88E246D2782AE2
b = 0713612DCDDCB40AAB946BDA29CA91F73AF958AFD9
x = 0369979697AB43897789566789567F787A7876A654
y = 00435EDB42EFAFB2989D51FEFCE3C80988F41FF883
</code></pre>
<p>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.</p>
<p>This was what I deed in sage:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/8919/computing-order-of-elliptic-curves-over-binary-field/?answer=37083#post-id-37083The 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](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)Sat, 25 Mar 2017 19:06:33 +0100https://ask.sagemath.org/question/8919/computing-order-of-elliptic-curves-over-binary-field/?answer=37083#post-id-37083