#11448: Basic implementation of point counting using canonical lift for elliptic
curve.
-------------------------------+--------------------------------------------
Reporter: jpflori | Owner: cremona
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.7.1
Component: elliptic curves | Keywords: point counting, satoh,
elliptic curve, canonical lift
Work_issues: Fix F_8 | Upstream: N/A
Reviewer: | Author: Jean-Pierre Flori
Merged: | Dependencies:
-------------------------------+--------------------------------------------
Changes (by jpflori):
* work_issues: => Fix F_8
Old description:
> 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 characteristic 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.
New description:
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.
--
Comment:
I just realized there is a bug when working over F_8.
I'll try to fix it quickly.[[BR]]
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11448#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
