implement Mestre's algorithm for constructing genus 2 hyperelliptic curves

[ncalexan]

*** this ticket is still using the old workflow, just apply patches and ignore the "branch" field ***

An implementation of Mestre's algorithm for reconstructing genus 2 hyperelliptic curves from their invariants.

This is limited to fields of characteristic not 2, 3, 5 and to curves with automorphism group generated by the hyperelliptic involution. Curve equations are not reduced, hence are unusably large over QQ, but see below.

That's it. Various other tickets deal with extensions:

• reduction of (the discriminant of) hyperelliptic curve models over the rationals #14755 reduces the discriminant of the hyperelliptic curve (essential for getting usable models over number fields)
• The Stoll-Cremona reduction method for hyperelliptic curves over number fields #14756 reduces the hyperelliptic curve equation once the discriminant is minimal (also essential for getting usable models over number fields).
• Implementing an algorithm for contructing genus 2 hyperelliptic curves with extra automorphism #12199 treats the case of larger automorphism groups
• Implementing an algorithm for contructing genus 2 hyperelliptic curves over fields of characteristic 2 #12200 is about characteristic 2, 3, 5

Apply:

• attachment: 6341.patch

CC: @ncalexan @mstreng @jpflori @sagetrac-lassina @fredstro

Component: number theory

Keywords: mestre algorithm genus 2 hyperelliptic curves sd35 sd51

Author: Florian Bouyer, Marco Streng

Branch: u/fstromberg/ticket/6341

Reviewer: Lassina Dembele, Fredrik Stromberg, Aly Deines

Merged: sage-5.13.beta0

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

[ncalexan]

Attachment: trac_6341-mestre-extcode.patch.gz

[ncalexan]

comment:2

Attachment: trac_6341-mestre.patch.gz

Here's a work in progress version. The extcode patch

• updates Denis Simon's pari qfsolve program;
• and incorporates Paul van Wamelen's pari genus 2 package.

The main devel patch integrates everything, or at least starts to.

[mstreng]

Attachment: trac_6341-mestre-without-conic.patch.gz

[mstreng]

comment:4

Attachment: trac_6341-mestre-extcode-without-qfsolve.patch.gz

The files "-without..." are the same as ncalexan's files, but with the Conic class removed and put in a separate patch at ticket 727. They still need the Conic class, but it may be better to view this as a separate enhancement.

[mstreng]

comment:5

This will be revived as part of a student project in August 2011.

[mstreng]

Changed keywords from mestre algorithm genus 2 hyperelliptic curves to mestre algorithm genus 2 hyperelliptic curves sd35

[mstreng]

Author: Florian Bouyer

[mstreng]

comment:6

Code was written by Florian Bouyer in September 2011, it works very nicely. Now it is a coding sprint at Sage Days 35 to put this in.

[sagetrac-florian]

Attachment: trac_6341_mestre_algorithm.patch.gz

An implementation of Mestre Algorithm

[mstreng]

comment:8

apply trac_6341_mestre_algorithm.patch

(this helps patchbot)

[mstreng]

comment:9

See also #12199, which will later fill in some special cases.

[sagetrac-florian]

comment:10

See also #12200, which will later fill in some special case

[sagetrac-florian]

minor changes to first patch

[sagetrac-florian]

comment:11

Attachment: trac_6341_mestre_algoritm_2.patch.gz

I corrected some typos and wasted white spaces pointed out by Marco

[mstreng]

comment:13

I'm reviewing and writing a reviewer's patch. Looks very good, but some small changes are needed that are easier to do than to explain.

[mstreng]

Reviewer: Marco Streng

[mstreng]

Attachment: 6341-more-corrections.patch.gz

Attachment: 6341-more-corrections.2.patch.gz

[mstreng]

Changed work issues from correct ticket number in error message, not 5534, but 14755 to complete references (title and journal with volume)

[mstreng]

comment:30

Attachment: 6341-more-corrections.3.patch.gz

(testing now)

[mstreng]

Changed work issues from complete references (title and journal with volume) to none

[mstreng]

Changed reviewer from Lassina Dembele to Lassina Dembele, Fredrik Stromberg

[mstreng]

comment:31

for patchbot:
apply 6341-mestre-only.patch and trac_6341-mestre-only_cleanup.patch and 6341-mestre-corrections.3.patch

[mstreng]

comment:33

apply 6341-mestre-only.patch and trac_6341-mestre-only_cleanup.patch and 6341-more-corrections.3.patch

[mstreng]

comment:34

I combined the patches into one, for easier review. Apply only 6341.patch

[mstreng]

ascii version of what was uploaded earlier this week

[fchapoton]

comment:35

Attachment: 6341.patch.gz

apply only 6341.patch

[adeines]

comment:36

This is working for me. I've verified several more non-CM examples in Magma.

[adeines]

Changed reviewer from Lassina Dembele, Fredrik Stromberg to Lassina Dembele, Fredrik Stromberg, Aly Deines

[jdemeyer]

Merged: sage-5.13.beta0