Opened 10 years ago
Closed 6 years ago
#6341 closed enhancement (fixed)
implement Mestre's algorithm for constructing genus 2 hyperelliptic curves
Reported by: | ncalexan | Owned by: | was |
---|---|---|---|
Priority: | major | Milestone: | sage-5.13 |
Component: | number theory | Keywords: | mestre algorithm genus 2 hyperelliptic curves sd35 sd51 |
Cc: | ncalexan, mstreng, jpflori, lassina, fstromberg | Merged in: | sage-5.13.beta0 |
Authors: | Florian Bouyer, Marco Streng | Reviewers: | Lassina Dembele, Fredrik Stromberg, Aly Deines |
Report Upstream: | N/A | Work issues: | |
Branch: | u/fstromberg/ticket/6341 (Commits) | Commit: | |
Dependencies: | Stopgaps: |
Description (last modified by )
* 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:
- #14755 reduces the discriminant of the hyperelliptic curve (essential for getting usable models over number fields)
- #14756 reduces the hyperelliptic curve equation once the discriminant is minimal (also essential for getting usable models over number fields).
- #12199 treats the case of larger automorphism groups
- #12200 is about characteristic 2, 3, 5
Apply:
Attachments (20)
Change History (58)
comment:1 Changed 10 years ago by
- Description modified (diff)
Changed 10 years ago by
Changed 10 years ago by
comment:2 Changed 10 years ago by
- Summary changed from implement Mestre's algorithm for constructing genus 2 hyperelliptic curves to [with patch, needs work] implement Mestre's algorithm for constructing genus 2 hyperelliptic curves
comment:3 Changed 10 years ago by
- Cc mstreng added
Changed 10 years ago by
Changed 10 years ago by
comment:4 Changed 10 years ago by
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.
comment:5 Changed 8 years ago by
- Report Upstream set to N/A
This will be revived as part of a student project in August 2011.
comment:6 Changed 8 years ago by
- Keywords sd35 added
- Summary changed from [with patch, needs work] implement Mestre's algorithm for constructing genus 2 hyperelliptic curves to implement Mestre's algorithm for constructing genus 2 hyperelliptic curves
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.
comment:7 Changed 8 years ago by
- Status changed from needs_work to needs_review
comment:8 Changed 8 years ago by
- Description modified (diff)
apply trac_6341_mestre_algorithm.patch
(this helps patchbot)
comment:9 Changed 8 years ago by
See also #12199, which will later fill in some special cases.
comment:10 Changed 8 years ago by
See also #12200, which will later fill in some special case
comment:11 Changed 8 years ago by
- Description modified (diff)
I corrected some typos and wasted white spaces pointed out by Marco
comment:12 Changed 8 years ago by
- Description modified (diff)
comment:13 Changed 8 years ago by
- Description modified (diff)
- Reviewers set to Marco Streng
- Status changed from needs_review to needs_work
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.
Changed 8 years ago by
Changed 8 years ago by
comment:14 follow-up: ↓ 15 Changed 8 years ago by
- Description modified (diff)
I wrapped lines and clarified / corrected documentation and corrected some formulas. I also removed functions that were not needed.
To do:
- continue with wrapping lines and checking documentation for spelling or formatting problems
- add the missing examples and possibly some more with non-trivial reduction properties
- remove functions marked with "to_remove"
- make sure stoll-cremona reduction is correctly implemented when homogenized to higher degree than the degree of the polynomial
- add a sanity check at the end of HyperellipticCurve_from_invariants, checking if the curve has the correct invariants before outputting it (RuntimeError? otherwise)
apply 6341_combined.patch
comment:15 in reply to: ↑ 14 Changed 8 years ago by
- Priority changed from minor to major
- Work issues set to see [comment:14]
comment:16 Changed 8 years ago by
- Cc jpflori added
comment:17 Changed 8 years ago by
With a view towards the future (number fields), it may be a good idea to move the code from lines 679 -- 732 to a separate function with input a polynomial, a valuation and a uniformizer. If the uniformizer generates the prime ideal, this gives a local reduction that does not screw up the other primes. If this is not possible (e.g. a non-principal prime of a number field) you can still get a local reduction and combine the local reductions later.
Changed 8 years ago by
version under construction, apply on top of previous patch, supposed to work for number fields, requires #11455
Changed 7 years ago by
Changed 7 years ago by
comment:18 Changed 7 years ago by
- Description modified (diff)
Changed 7 years ago by
comment:19 Changed 6 years ago by
- Description modified (diff)
I separated off the (huge) reduction code from this simple functionality. Hopefully that helps in finishing this ticket.
comment:20 Changed 6 years ago by
instructions for the patchbot :
apply 6341-mestre-only.patch
comment:21 Changed 6 years ago by
- Description modified (diff)
here is patch, just cleaning things up. There are some doctests failing..
apply 6341-mestre-only.patch trac_6341-mestre-only_cleanup.patch
Changed 6 years ago by
comment:22 Changed 6 years ago by
- Keywords sd51 added
comment:23 Changed 6 years ago by
- Cc lassina added
Changed 6 years ago by
comment:24 Changed 6 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
comment:25 Changed 6 years ago by
- Cc fstromberg added
- Reviewers Marco Streng deleted
- Work issues see [comment:14] deleted
comment:26 Changed 6 years ago by
- Branch set to u/fstromberg/ticket/6341
comment:27 Changed 6 years ago by
- Status changed from needs_review to needs_work
- Work issues set to correct ticket number in error message, not 5534, but 14755
comment:28 Changed 6 years ago by
- Description modified (diff)
- Reviewers set to Lassina Dembele
- Status changed from needs_work to needs_review
Changed 6 years ago by
comment:29 Changed 6 years ago by
- Status changed from needs_review to needs_work
- Work issues changed from correct ticket number in error message, not 5534, but 14755 to complete references (title and journal with volume)
Changed 6 years ago by
comment:30 Changed 6 years ago by
- Description modified (diff)
- Reviewers changed from Lassina Dembele to Lassina Dembele, Fredrik Stromberg
- Work issues complete references (title and journal with volume) deleted
(testing now)
comment:31 follow-up: ↓ 33 Changed 6 years ago by
- Description modified (diff)
for patchbot: apply 6341-mestre-only.patch and trac_6341-mestre-only_cleanup.patch and 6341-mestre-corrections.3.patch
comment:32 Changed 6 years ago by
- Status changed from needs_work to needs_review
comment:33 in reply to: ↑ 31 Changed 6 years ago by
apply 6341-mestre-only.patch and trac_6341-mestre-only_cleanup.patch and 6341-more-corrections.3.patch
comment:34 Changed 6 years ago by
- Description modified (diff)
I combined the patches into one, for easier review. Apply only 6341.patch
comment:35 Changed 6 years ago by
apply only 6341.patch
comment:36 Changed 6 years ago by
- Reviewers changed from Lassina Dembele, Fredrik Stromberg to Lassina Dembele, Fredrik Stromberg, Aly Deines
- Status changed from needs_review to positive_review
This is working for me. I've verified several more non-CM examples in Magma.
comment:37 Changed 6 years ago by
- Milestone changed from sage-feature to sage-5.13
comment:38 Changed 6 years ago by
- Merged in set to sage-5.13.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
Here's a work in progress version. The extcode patch
The main devel patch integrates everything, or at least starts to.