Basic implementation of point counting using canonical lift for elliptic curve.

[jpflori]

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.

CC: @jpflori @mminzlaff @defeo @zimmermann6

Component: elliptic curves

Keywords: point counting, satoh, canonical lift

Work Issues: Fix F_8

Author: Jean-Pierre Flori

Issue created by migration from https://trac.sagemath.org/ticket/11448

[jpflori]

Attachment: trac_11448-fgh_pari.patch.gz

Basic implementation.

[jpflori]

comment:2

I just realized there is a bug when working over F_8.

I'll try to fix it quickly.

[jpflori]

Work Issues: Fix F_8

[roed314]

comment:5

Any progress on this?

[jpflori]

comment:6

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.

[kedlaya]

comment:11

There is a ticket about exposing the PARI implementation at #16931.

[jpflori]

comment:12

This is way out of date and should be closed!

[jpflori]

comment:13

Superseded by #16931.

[embray]

comment:14

Determined to be invalid/duplicate/wontfix (closing as "wontfix" as a catch-all resolution).