Ticket #11448 (new enhancement)
Basic implementation of point counting using canonical lift for elliptic curve.
|Reported by:||jpflori||Owned by:||cremona|
|Component:||elliptic curves||Keywords:||point counting, satoh, elliptic curve, canonical lift|
|Cc:||jpflori, minz, defeo, zimmerma||Work issues:||Fix F_8|
|Authors:||Jean-Pierre Flori||Merged in:|
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.
- Description modified (diff)
- Work issues set to Fix F_8