Opened 10 years ago

Last modified 12 months ago

#13376 needs_info enhancement

Optional SPKG for SmallJac — at Initial Version

Reported by: pavpanchekha Owned by: tbd
Priority: major Milestone: sage-wishlist
Component: packages: optional Keywords:
Cc: jpflori, kedlaya Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Smalljac is a library and set of programs for computing L-polynomials and Jacobian group structures of low genus curves over finite fields. Given a curve C of genus 1 or 2 defined over Q or a quadratic number field, it will efficiently compute either the sequence of L-polynomials or Jacobian group structures arising from the reduction of C at all primes of good reduction up to a specified norm bound.

This set of SPKGs and the corresponding patch to Sage 5.2 add support for using smallJac from Sage.

  • EllipticCurve.aplist can be run with algorithm="smalljac", yielding run times of six times faster on a single core.
  • EllipticCurve.aplists provides more usable representation the above, and supports number fields (multiple reductions per prime norm). See the documentation for more, but in general aplist couldn't be made very easy to use for the number field case.
  • EllipticCurve.grouplists gives the abelian groups isomorphic to various reductions of a curve.
  • EllipticCurve.lpolylists yields the L-Polynomials of reductions of a curve.
  • EllipticCurve.guess_sato_tate_group attempts to guess the Sato-Tate group of the Jacobian of a curve of genus 1 or 2 based on the distribution of its L-polynomial coefficients.
  • EllipticCurve.moments yields the moments of the distribution of coefficients of the L-Polynomials.
  • EllipticCurve.trace_histogram gives a very simple histogram for the distribution of traces of Frobenius of a curve, reduced at a range of primes.

For all of the above methods (except aplist), identical functionality exists (with the same name) for genus 2 curves. All of the above methods also parallelize over multiple cores (currently, to a power of two cores). For large problems, this achieves approximately linear speedup; for example, computing the first billion traces of Frobenius of an ordinary elliptic curve is 178 times faster on 32 cores.

For each of these features, there is Sage documentation docstring-style documentation.

The SPKGs only compile and work on 64-bit machines, since SmallJac? only supports 64-bit architectures, and require GMP. Two SPKGs are provided, since SmallJac? depends on ff_poly, but so does some of Drew Sutherland's other code, so it makes sense to split the two. They've been tested to work on a completely clean install of Sage on at least two differently-configured machines.

The patch has been tested to apply cleanly to 5.2.

Change History (3)

Changed 10 years ago by pavpanchekha

SPKG for ff_poly

Changed 10 years ago by pavpanchekha

SPKG for smalljac

Changed 10 years ago by pavpanchekha

Patch to Sage 5.2 to support interfacing with SmallJac?

Note: See TracTickets for help on using tickets.