Opened 9 years ago
Closed 4 years ago
#11448 closed enhancement (wontfix)
Basic implementation of point counting using canonical lift for elliptic curve.
Reported by: | jpflori | Owned by: | cremona |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | elliptic curves | Keywords: | point counting, satoh, elliptic curve, canonical lift |
Cc: | jpflori, minz, defeo, zimmerma | Merged in: | |
Authors: | Jean-Pierre Flori | Reviewers: | |
Report Upstream: | N/A | Work issues: | Fix F_8 |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
The proposed patch implements a basic version of point counting for elliptic curve using canonical lift (à la Satoh).
This implements the algorithms described in Fouquet, Gaudry and Harley, "An extension of Satoh's algorithm and its implementation", http://hal.inria.fr/inria-00512791/en, based on the Pari/GP implementation by Yeoh, http://pages.cs.wisc.edu/~yeoh/nt/satoh-fgh.gp.
It uses Pari for computation in Z_q.
This is currently only implemented for characteristic two.
Other characteristics are nearly done, but I have some bugs left.
It adds a cardinality_fgh() method to the EllipticCurve_finite_field class and the real implementation is made in a new fgh_algo.py file.
Attachments (1)
Change History (15)
Changed 9 years ago by
comment:1 follow-up: ↓ 2 Changed 9 years ago by
- Cc minz added
comment:2 in reply to: ↑ 1 Changed 9 years ago by
- Description modified (diff)
- Work issues set to Fix F_8
I just realized there is a bug when working over F_8.
I'll try to fix it quickly.
comment:3 Changed 9 years ago by
- Cc defeo added
comment:4 Changed 9 years ago by
- Cc zimmerma added
comment:5 Changed 7 years ago by
Any progress on this?
comment:6 Changed 7 years ago by
PARI now has very efficient point counting in small characteristic (faster than MAGMA), we should wrap these functionnalities. I have as well code based on FLINT yielding similar performance as PARI.
I've put some timings of the PARI code (originally posted on pari-dev list) at #11548.
comment:7 Changed 7 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:8 Changed 6 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:9 Changed 6 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:10 Changed 6 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:11 Changed 4 years ago by
There is a ticket about exposing the PARI implementation at #16931.
comment:12 Changed 4 years ago by
- Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
- Status changed from new to needs_review
This is way out of date and should be closed!
comment:13 Changed 4 years ago by
- Status changed from needs_review to positive_review
Superseded by #16931.
comment:14 Changed 4 years ago by
- Resolution set to wontfix
- Status changed from positive_review to closed
Determined to be invalid/duplicate/wontfix (closing as "wontfix" as a catch-all resolution).
Basic implementation.