Ticket #11448 (new enhancement)
Basic implementation of point counting using canonical lift for elliptic curve.
| Reported by: | jpflori | Owned by: | cremona |
|---|---|---|---|
| Priority: | major | Milestone: | sage-5.10 |
| Component: | elliptic curves | Keywords: | point counting, satoh, elliptic curve, canonical lift |
| Cc: | jpflori, minz, defeo, zimmerma | Work issues: | Fix F_8 |
| Report Upstream: | N/A | Reviewers: | |
| Authors: | Jean-Pierre Flori | Merged in: | |
| Dependencies: | Stopgaps: |
Description (last modified by jpflori) (diff)
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
-
trac_11448-fgh_pari.patch
(12.3 KB) -
added by jpflori 2 years ago.
- Basic implementation.
Change History
Changed 2 years ago by jpflori
-
attachment
trac_11448-fgh_pari.patch
added
comment:2 in reply to: ↑ 1 Changed 2 years ago by jpflori
- 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:6 Changed 7 months ago by jpflori
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.
Basic implementation.