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()
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.
On 12 June 2012 14:39, wedi kese <mehzer...@gmail.com> wrote:
> 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?
> --
> You received this message because you are subscribed to the Google Groups "sage-nt" group.
> To post to this group, send an email to sage-nt@googlegroups.com.
> To unsubscribe from this group, send email to sage-nt+unsubscribe@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/sage-nt?hl=en-GB.
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:
> 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.
> On 12 June 2012 14:39, wedi kese <mehzer...@gmail.com> wrote:
> > 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?
> > --
> > You received this message because you are subscribed to the Google
> Groups "sage-nt" group.
> > To post to this group, send an email to sage-nt@googlegroups.com.
> > To unsubscribe from this group, send email to
> sage-nt+unsubscribe@googlegroups.com.
> > For more options, visit this group at
> http://groups.google.com/group/sage-nt?hl=en-GB.
> --
> You received this message because you are subscribed to the Google Groups
> "sage-nt" group.
> To post to this group, send an email to sage-nt@googlegroups.com.
> To unsubscribe from this group, send email to
> sage-nt+unsubscribe@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),
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"
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.
> On Tue, Jun 12, 2012 at 4:58 PM, John Cremona <john.crem...@gmail.com>
> wrote:
>> 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.
>> On 12 June 2012 14:39, wedi kese <mehzer...@gmail.com> wrote:
>> > 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?
>> > --
>> > You received this message because you are subscribed to the Google
>> > Groups "sage-nt" group.
>> > To post to this group, send an email to sage-nt@googlegroups.com.
>> > To unsubscribe from this group, send email to
>> > sage-nt+unsubscribe@googlegroups.com.
>> > For more options, visit this group at
>> > http://groups.google.com/group/sage-nt?hl=en-GB.
>> --
>> You received this message because you are subscribed to the Google Groups
>> "sage-nt" group.
>> To post to this group, send an email to sage-nt@googlegroups.com.
>> To unsubscribe from this group, send email to
>> sage-nt+unsubscribe@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),
> 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"
> --
> You received this message because you are subscribed to the Google Groups
> "sage-nt" group.
> To post to this group, send an email to sage-nt@googlegroups.com.
> To unsubscribe from this group, send email to
> sage-nt+unsubscribe@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/sage-nt?hl=en-GB.
> 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.
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:
> 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 to this group, send an email to sage-nt@googlegroups.com.
> To unsubscribe from this group, send email to
> sage-nt+unsubscribe@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),
Addis Ababa, Ethiopia.
" Joy is not the absence of suffering but the presence of God"
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
On 18 June 2012 11:06, Mehari Zeraberuk <mehzer...@gmail.com> wrote:
> 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:
>>> 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 to this group, send an email to sage-nt@googlegroups.com.
>> To unsubscribe from this group, send email to
>> sage-nt+unsubscribe@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),
> Addis Ababa, Ethiopia.
> " Joy is not the absence of suffering but the presence of God"
> --
> You received this message because you are subscribed to the Google Groups
> "sage-nt" group.
> To post to this group, send an email to sage-nt@googlegroups.com.
> To unsubscribe from this group, send email to
> sage-nt+unsubscribe@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/sage-nt?hl=en-GB.
