Opened 6 years ago
Closed 6 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(p^{m}) if m|n. Also #1119 still relies on floating point arithmetic.
Attachments (1)
Change History (9)
comment:1 Changed 6 years ago by malb
Changed 6 years ago by gmoose05
comment:2 follow-up: ↓ 5 Changed 6 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 6 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 6 years ago by mabshoff
Applied 8312.patch to Sage 2.10.2.alpha0
comment:5 in reply to: ↑ 2 Changed 6 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 6 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 6 years ago by cremona
The issues raised here have all been sorted under other tickets. This one can be closed.
comment:8 Changed 6 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.
that should be #1120 instead of #1119