The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Computing order of elliptic curves over binary field
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 7 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Jun 12 2012, 9:39 am
From: wedi kese <mehzer...@gmail.com>
Date: Tue, 12 Jun 2012 06:39:22 -0700 (PDT)
Local: Tues, Jun 12 2012 9:39 am
Subject: Computing order of elliptic curves over binary field
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()

To post a message you must first join this group.
You do not have the permission required to post.
More options Jun 12 2012, 9:58 am
From: John Cremona <john.crem...@gmail.com>
Date: Tue, 12 Jun 2012 14:58:20 +0100
Local: Tues, Jun 12 2012 9:58 am
Subject: Re: [sage-nt] Computing order of elliptic curves over binary field
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

John Cremona

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.

On 12 June 2012 14:39, wedi kese <mehzer...@gmail.com> wrote:

To post a message you must first join this group.
You do not have the permission required to post.
More options Jun 12 2012, 10:18 am
From: Mehari Zeraberuk <mehzer...@gmail.com>
Date: Tue, 12 Jun 2012 17:18:14 +0300
Local: Tues, Jun 12 2012 10:18 am
Subject: Re: [sage-nt] Computing order of elliptic curves over binary field

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.

On Tue, Jun 12, 2012 at 4:58 PM, John Cremona <john.crem...@gmail.com>wrote:

--
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

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jun 12 2012, 10:23 am
From: John Cremona <john.crem...@gmail.com>
Date: Tue, 12 Jun 2012 15:23:10 +0100
Local: Tues, Jun 12 2012 10:23 am
Subject: Re: [sage-nt] Computing order of elliptic curves over binary field
On 12 June 2012 15:18, Mehari Zeraberuk <mehzer...@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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jun 18 2012, 4:44 am
From: Jean-Pierre Flori <jpfl...@gmail.com>
Date: Mon, 18 Jun 2012 01:44:09 -0700 (PDT)
Local: Mon, Jun 18 2012 4:44 am
Subject: Re: [sage-nt] Computing order of elliptic curves over binary field

> 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.

To post a message you must first join this group.
You do not have the permission required to post.
More options Jun 18 2012, 5:06 am
From: Mehari Zeraberuk <mehzer...@gmail.com>
Date: Mon, 18 Jun 2012 12:06:41 +0300
Local: Mon, Jun 18 2012 5:06 am
Subject: Re: [sage-nt] Computing order of elliptic curves over binary field

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.

On Mon, Jun 18, 2012 at 11:44 AM, Jean-Pierre Flori <jpfl...@gmail.com>wrote:

--
Mehari Zeraberuk Gebrezgi,
Masters of Technology in Computer Science and Engineering (MTech),

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jun 18 2012, 12:53 pm
From: John Cremona <john.crem...@gmail.com>
Date: Mon, 18 Jun 2012 18:53:54 +0200
Local: Mon, Jun 18 2012 12:53 pm
Subject: Re: [sage-nt] Computing order of elliptic curves over binary field
In case it helps, I am currently at the same meeting as Bill A and can
this week, but I will not be mentioning the binary case.

John

On 18 June 2012 11:06, Mehari Zeraberuk <mehzer...@gmail.com> wrote: