Opened 7 years ago

Closed 7 years ago

#1121 closed enhancement (fixed)

improve point counting for curvers over extension fields

Reported by: malb Owned by: was
Priority: major Milestone: sage-3.0
Component: algebraic geometry Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

John Cremona wrote

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.

See http://groups.google.com/group/sage-devel/browse_thread/thread/69ebf55ee4f22278/23c61ad57cbff62a

#1119 implements to computing over GF(p) if possible, but it doesn't implement computing over GF(pm) if m|n. Also #1119 still relies on floating point arithmetic.

Attachments (1)

8312.patch (817 bytes) - added by gmoose05 7 years ago.

Download all attachments as: .zip

Change History (9)

comment:1 Changed 7 years ago by malb

that should be #1120 instead of #1119

Changed 7 years ago by gmoose05

comment:2 follow-up: Changed 7 years ago by gmoose05

  • Milestone changed from sage-feature to sage-2.10.2

8312 just corrects minor thing in documentation

The Documentation said the cardinality was not cached, but in fact the code does cache.

comment:3 Changed 7 years ago by robertwb

  • Summary changed from improve point counting for curvers over extension fields to [with positive review] improve point counting for curvers over extension fields

Yep, looks good to me.

comment:4 Changed 7 years ago by mabshoff

Applied 8312.patch to Sage 2.10.2.alpha0

comment:5 in reply to: ↑ 2 Changed 7 years ago by malb

Replying to gmoose05:

8312 just corrects minor thing in documentation

The Documentation said the cardinality was not cached, but in fact the code does cache.

I am confused. Does the patch address the ticket?

comment:6 Changed 7 years ago by mabshoff

  • Summary changed from [with positive review] improve point counting for curvers over extension fields to improve point counting for curvers over extension fields

I don't think that the patch addresses the ticket, it just corrects the issue about caching. So I am removing the with positive review - I guess we should have opened another ticket for the documentation issue.

Cheers,

Michael

comment:7 Changed 7 years ago by cremona

The issues raised here have all been sorted under other tickets. This one can be closed.

comment:8 Changed 7 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from new to closed

Closing this on the recommendation of John Cremona since the issues have all been fixed.

Note: See TracTickets for help on using tickets.