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
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
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
--
John Cremona
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-----
see
http://trac.sagemath.org/sage_trac/ticket/1120
and
http://trac.sagemath.org/sage_trac/ticket/1121
for the low hanging fruits.
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
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
--
John Cremona