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 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.

Attachments (1)

trac_11448-fgh_pari.patch (12.3 KB) - added by jpflori 9 years ago.
Basic implementation.

Download all attachments as: .zip

Change History (15)

Changed 9 years ago by jpflori

Basic implementation.

comment:1 follow-up: Changed 9 years ago by minz

  • Cc minz added

comment:2 in reply to: ↑ 1 Changed 9 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:3 Changed 9 years ago by defeo

  • Cc defeo added

comment:4 Changed 9 years ago by zimmerma

  • Cc zimmerma added

comment:5 Changed 7 years ago by roed

Any progress on this?

comment:6 Changed 7 years 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.

comment:7 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:8 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:9 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:10 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:11 Changed 4 years ago by kedlaya

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

comment:12 Changed 4 years ago by jpflori

  • 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 jpflori

  • Status changed from needs_review to positive_review

Superseded by #16931.

comment:14 Changed 4 years ago by embray

  • 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).

Note: See TracTickets for help on using tickets.