point counting

1 view
Skip to first unread message

Martin Albrecht

unread,
Nov 6, 2007, 2:09:06 PM11/6/07
to Sage Development
I stumbled over #262

http://trac.sagemath.org/sage_trac/ticket/262

again. Here Graeme Taylor proposes his implementation of point counting of
elliptic curves over GF(p^n) with coefficients in GF(p) in Weierstrass form.

He describes the background at:

http://maths.straylight.co.uk/archives/69

. This was turned down because a patch by Alex Ghitza

http://www.sagemath.org/hg/sage-main/rev/57bc9076e61a

implements the same functionality. I can see that this implements the same
functionality but I find the interface rather complicated: The user is
required to construct the curve over the prime subfield and ask for the
cardinality over a higher degree extension via an optional
parameter 'degree'. E.g.

sage: k.<a> = GF(7^10)
sage: E = EllipticCurve(k,[5,2])
sage: E2 = EllipticCurve(k.base_ring(), E.a_invariants()) # down
sage: E2.cardinality(10) # and up again
282464343

I wonder why not just compute the cardinality using this method by default if
all coefficients lie in the prime subfield? Is this optional 'degree'
parameter really necessary?

Just curious,
Martin

--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_www: http://www.informatik.uni-bremen.de/~malb
_jab: martinr...@jabber.ccc.de

Robert Bradshaw

unread,
Nov 6, 2007, 2:31:05 PM11/6/07
to sage-...@googlegroups.com

I agree. I actually started to implement this function, but never
submitted it because I saw someone else had beat met to it. One
should not have to provide the "degree" parameter--it should be
automatically deduced (e.g. if E is over GF(p^n) with coefficents in
GF(p^m), the computation should be performed in GF(p^m) then extended.)

- Robert

John Cremona

unread,
Nov 6, 2007, 2:36:36 PM11/6/07
to sage-...@googlegroups.com
You are right of course -- one should always compute the order over
the smallest field of definition and then use the easy formula to get
the order of E(GF(q^d)) from that of E(GF(q)).

While you are at it you should not stop at the smallest field
containing the coefficients of the given curve, it would be enough to
work over the field containing the j-invariant, plus a little work
deciding which twist your need and all this is as usual a little more
complicated when j=0 or j=1728, or in characteristics 2 and 3.

This feels like reinventing wheels -- i wonder who has done this already?

As for implementation, it is *extremely* ugly to work with floating
point complex numbers for this (as both Graeme and Alex seem to do.
It should be done algebraically!

If n = #E(GF(q)) then a=1+q-n is the trace of alpha =
(a+sqrt(a^2-4*q))/2, and then #E(GF(q^d)) = 1+q^d-trace(alpha^d). The
trace of the d'th power of alpha is just a resultant calculation.

John


--
John Cremona

John Cremona

unread,
Nov 6, 2007, 2:39:38 PM11/6/07
to sage-...@googlegroups.com
I thought this looked familiar! See my post at
http://pari.math.u-bordeaux.fr/archives/pari-users-0406/msg00001.html

John


--
John Cremona

Alex Ghitza

unread,
Nov 6, 2007, 7:08:03 PM11/6/07
to sage-...@googlegroups.com
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Martin, Robert, John,

I was not terribly happy with my implementation either, but thought I'd
put it in and keep working on it, or maybe that it would incite others
to fix it :)

I'll be happy to implement the changes suggested by you as soon as I get
a chance (teaching 3 different courses in one semester is more
time-consuming than one might think), probably this weekend. Of course,
I won't be upset if someone else beats me to it.

Alex

Martin Albrecht wrote:
> I stumbled over #262
>
> http://trac.sagemath.org/sage_trac/ticket/262
>
> again. Here Graeme Taylor proposes his implementation of point counting of
> elliptic curves over GF(p^n) with coefficients in GF(p) in Weierstrass form.
>
> He describes the background at:
>
> http://maths.straylight.co.uk/archives/69
>
> . This was turned down because a patch by Alex Ghitza
>
> http://www.sagemath.org/hg/sage-main/rev/57bc9076e61a
>
> implements the same functionality. I can see that this implements the same
> functionality but I find the interface rather complicated: The user is
> required to construct the curve over the prime subfield and ask for the
> cardinality over a higher degree extension via an optional
> parameter 'degree'. E.g.
>
> sage: k.<a> = GF(7^10)
> sage: E = EllipticCurve(k,[5,2])
> sage: E2 = EllipticCurve(k.base_ring(), E.a_invariants()) # down
> sage: E2.cardinality(10) # and up again
> 282464343
>
> I wonder why not just compute the cardinality using this method by default if
> all coefficients lie in the prime subfield? Is this optional 'degree'
> parameter really necessary?
>
> Just curious,
> Martin
>

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHMQHjdZTaNFFPILgRAtHnAJ4+UoLNqkecVJJWc01q2ngqbrsYQACfV209
qzwu+loG9FlRS1K2XiLrggA=
=D76a
-----END PGP SIGNATURE-----

Martin Albrecht

unread,
Nov 7, 2007, 10:59:45 AM11/7/07
to sage-...@googlegroups.com

Martin Albrecht

unread,
Nov 8, 2007, 6:54:00 PM11/8/07
to sage-...@googlegroups.com
> I agree. I actually started to implement this function, but never
> submitted it because I saw someone else had beat met to it. One
> should not have to provide the "degree" parameter--it should be
> automatically deduced (e.g. if E is over GF(p^n) with coefficents in
> GF(p^m), the computation should be performed in GF(p^m) then extended.)

Wow, that e-mail arrived here *just now*. Something is wrong with Google
groups.

William Stein

unread,
Nov 9, 2007, 2:30:21 AM11/9/07
to sage-...@googlegroups.com
On Nov 8, 2007 11:54 PM, Martin Albrecht <ma...@informatik.uni-bremen.de> wrote:
> > I agree. I actually started to implement this function, but never
> > submitted it because I saw someone else had beat met to it. One
> > should not have to provide the "degree" parameter--it should be
> > automatically deduced (e.g. if E is over GF(p^n) with coefficents in
> > GF(p^m), the computation should be performed in GF(p^m) then extended.)
>
> Wow, that e-mail arrived here *just now*. Something is wrong with Google
> groups.

FYI: I saw the above-mentioned message from Robert Bradshaw 3 days
ago. I'm not sure what if any implications that has for your comment, except
that from my perspective the email list works fine. I wonder if there is
some issue with forwarding email from googlegroups to
ma...@informatik.uni-bremen.de?
I have my google group email going to my gmail email address. I wonder if you
changed yours to go there, then downloaded email from your gmail address,
if it would fix your problem...

William

Alex Ghitza

unread,
Nov 10, 2007, 2:43:55 PM11/10/07
to sage-...@googlegroups.com
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Martin,

The link to which John pointed us gives a very easy way of computing the
trace over F_q algebraically, without floating point arithmetic. All we
need to do is put John's one-liner PARI code in. I would love to do
this, but I don't know how to take your patch from ticket #1120, get it
into my Sage installation, modify it, and replace it on trac. Would you
mind doing this? Here are the changes (the line numbers are from your
patch):

replace lines 313 through 320 with the following:

tp=p+1-E.cardinality(algorithm=algorithm,early_abort=early_abort)
tq=pari('trace(Mod(x,x^2-'+str(tp)+'*x+'+str(p)+')^'+str(degree)+')')
N=q+1-tq


I believe that's it. Thanks, and thanks to John for pointing out how to
do this the proper way.

Best,
Alex


Martin Albrecht wrote:
> Hi all,
>
> see
>
> http://trac.sagemath.org/sage_trac/ticket/1120
>
> and
>
> http://trac.sagemath.org/sage_trac/ticket/1121
>
> for the low hanging fruits.
>
> Martin
>

-----BEGIN PGP SIGNATURE-----


Version: GnuPG v1.4.7 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHNgn7dZTaNFFPILgRAuxzAKCcvRXpGByn2MbJH6pvbcWliais5QCfaOX3
IE1yBzhCgrr0kAZ2fFHlKbo=
=n98G
-----END PGP SIGNATURE-----

John Cremona

unread,
Nov 10, 2007, 5:27:47 PM11/10/07
to sage-...@googlegroups.com
I hope we can do this at Dage Days 6 in the next few days.

John


--
John Cremona

Reply all
Reply to author
Forward
0 new messages