Computing order of elliptic curves over binary field

[wedi kese]

I have generated random elliptic curves over binary field based on the
available standards. And I want to know the number of points for each
elliptic curves.

I could compute for small values of elliptic curve parameters(a and b)
easily. However, when the parameters of the elliptic curve become more
1 words(32 bit machine), it displays exhaust memory. That means, it
exits without computing its order.

Do know a method on how to compute this order for elliptic curves
over binary field?

Sample code for sage notebook():
b = 6050472329188554790280330439765679504692881977845
Z.<x>=GF(2)[]
K.<a>=GF(2^163, 'a', modulus = x^163 + x^7 + x^6 + x^3 + 1)
bb = Z(b.digits(2))
E = EllipticCurve(K,[1, 1, 0, 0, bb])
P = E.random_element()
print E.order()

[John Cremona]

Sorry, for curves like this (the j-invariant is in GF(2^163) and has
degree 163) the current implementation is hopeless, as it uses
Baby-Step-Giant-Step with memory usage about q^(1/4), more than you
are likely to have.

There are certainly better methods for point-counting on large binary
fields, but they are not available in Sage right now. If you fancy
implementing something, go ahead!

John Cremona

PS With your field K,

sage: E =EllipticCurve(K,[1,1,0,0,1])
sage: E.order()
11692013098647223345629483507196896696658237148126

is instantaneous since it does the counting in GF(2), but that is as
clever as it gets.

> --
> You received this message because you are subscribed to the Google Groups "sage-nt" group.
> To post to this group, send an email to sag...@googlegroups.com.
> To unsubscribe from this group, send email to sage-nt+u...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/sage-nt?hl=en-GB.
>

[Mehari Zeraberuk]

You are right. The problem is on the algorithm(baby-step giant-step) for computing order of elliptic curves over binary curves. Is n't it possible to compute using satoh-fgh.gp algorithm which is available at this link http://pages.cs.wisc.edu/~yeoh/nt/satoh-fgh.gp to compute the order of elliptic curves over binary field. I think it is possible for elliptic curves of the form
y^2 + xy = x^3 + b but I don't know how to compute order of binary elliptic curves of the form y^2 + xy = x^3 + a*x^2 + b? Please help if know how to compute order of such elliptic curves using satoh-fgh.

--

Mehari Zeraberuk Gebrezgi,

Masters of Technology in Computer Science and Engineering (MTech),

Cisco Certified Network Associate (CCNA),

Available: Information Network Security Agency, INSA,

Phone: +251 920 95 86 39

Addis Ababa, Ethiopia.

" Joy is not the absence of suffering but the presence of God"

[John Cremona]

On 12 June 2012 15:18, Mehari Zeraberuk <mehz...@gmail.com> wrote:
>
> You are right.

Well, I wrote almost all the code for this in Sage now apart from the
SEA implementation.

> The problem is on the algorithm(baby-step giant-step) for
> computing order of elliptic curves over binary curves. Is n't it possible to
> compute using satoh-fgh.gp algorithm which is available at this link
> http://pages.cs.wisc.edu/~yeoh/nt/satoh-fgh.gp to compute the order of
> elliptic curves over binary field. I think it is possible for elliptic
> curves of the form
> y^2 + xy = x^3 + b but I don't know how to compute order of binary elliptic
> curves of the form y^2 + xy = x^3 + a*x^2 + b? Please help if know how to
> compute order of such elliptic curves using satoh-fgh.

A useful step would be to get that gp script (which says it is
"released into the public-domain") into Sage with an interface. That
would not be hard to do. For the general case, there are people more
expert than me.

John

[Jean-Pierre Flori]

A useful step would be to get that gp script (which says it is
"released into the public-domain") into Sage with an interface.  That
would not be hard to do.  For the general case, there are people more
expert than me.

I did it a while ago, basically rewriting Yeoh's code based on the FGH algo to use the libpari interface exposed in Sage.
I then modified the code to use a slightly more efficient method.
This is hidden somewhere in Trac (there was also a message here).

Anyway, the padics arithmetic is done quite wrongly with Pari. Moreover, pari exposes new structure for finite fields and so on since release 2.5 (that makes me even doubt that the old patches I wrote are still working with the latest Sage/Pari releases).
But, it let's you compute number of points on non-trivial extension of GF(2) where BSGS makes your memory blow up.

I'm also working on Flint implementation of such stuff.
This is definitely not ready for releases but should be in some months.

[Mehari Zeraberuk]

Yea, Thanks a lot! I deed it!

I have solved the problem I was facing to compute order of elliptic curves over binary field using satoh-fgh.gp script. The script computes order of elliptic curves of the form :    y^2 + xy = x^3 + b  ----equ(1). However, Proff. Bill Allombert has helped me to figure out how to compute elliptic curves of the form:                                y^2 + xy = x^3 + a*x^2 + b --equ(2). This can be computed by knowing the trace of the parameter a of the given elliptic curve.
That means, compute order of the given elliptic curve ignoring its a parameter. Next, compute order trace that parameter.
If trace(a) == 0 then order of elliptic curve of form equ(2) is equal to form of equ(1)
else order of equ(2) equals to 2*(2^n+1) - order of equ(1).

In this way, I have solved the problem.

--

You received this message because you are subscribed to the Google Groups "sage-nt" group.

To view this discussion on the web, visit https://groups.google.com/d/msg/sage-nt/-/oqnb9Y7P1wIJ.

To post to this group, send an email to sag...@googlegroups.com.
To unsubscribe from this group, send email to sage-nt+u...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/sage-nt?hl=en-GB.

--

Mehari Zeraberuk Gebrezgi,

Masters of Technology in Computer Science and Engineering (MTech),

[John Cremona]

In case it helps, I am currently at the same meeting as Bill A and can
ask him questions. I'll also be giving two talks about point-counting
this week, but I will not be mentioning the binary case.

John