I'm going to forward this to sage-nt as there may be people who read that but not this.
Meanwhile I would recommend getting something to work correctly before worrying too much about what is most efficient. John On Wed, 6 Mar 2024, 12:52 Giacomo Pope, <giacomop...@gmail.com> wrote: > *=== Summary* > > Arithmetic of divisors for Jacobians of hyperelliptic curves with two > points at infinity is not currently properly supported for SageMath. Worse, > there are no checks or error handling and the output of the arithmetic is > simply wrong. > > Minimal example: > > sage: R.<x> = PolynomialRing(GF(11)) > sage: f = x^6 + x + 1 > sage: H = HyperellipticCurve(f) > sage: J = H.jacobian() > sage: D = J(H.lift_x(1)) > sage: jacobian_order = sum(H.frobenius_polynomial()) > sage: jacobian_order * D > (x + 10, y + 5) # this should be (1) > > I wrote about this as a GitHub issue as well: > https://github.com/sagemath/sage/issues/37109 but I am now coming to > sage-devel as I have *some* progress and want to try and have advice / > conversation about how we can improve this. > > *=== Suggestion* > > I have been working on a small proof of concept for arithmetic with > Sabrina Kunzweiler using sage ( > https://github.com/GiacomoPope/HyperellipticCurves) which has been > implemented following the balanced strategy of the following paper: > > Efficient Hyperelliptic Arithmetic using Balanced Representation for > Divisors > Steven D. Galbraith, Michael Harrison, and David J. Mireles Morales > https://www.math.auckland.ac.nz/~sgal018/ANTS08.pdf > > This is similar but distinct to what Magma uses for arithmetic. > Essentially the arithmetic is the same as Cantor, but to ensure a unique > representation of the zero degree divisors there is an integer weight n > together with Mumford polynomials (u, v). By keeping track of this weight > during composition and reduction arithmetic is complete. We can ensure > deg(u) <= g by using composition and reduction at infinity. > > This implementation works as I expect and I am happy with it. But getting > it into Sage will be a bigger job. I will try and outline some of the > issues I see but as with everything the unknown unknowns will be the > biggest issue. > > Minimal working implementation: > https://github.com/GiacomoPope/HyperellipticCurves > > *=== Potential Issues* > > *Weighted projective models* > > The balanced representation is naturally tied to a weighted projective > model for the hyperelliptic curve (with weights (1 : 3 : 1)) which is much > less built out than unweighted polynomial rings in sagemath. > > Two recent issues with the weighted polynomial ring: > > https://github.com/sagemath/sage/issues/37155 > https://github.com/sagemath/sage/issues/37167 > > In our implementation I simply build the weighted projective model in a > normal polynomial ring by computing the correct weights but there could be > further complications if we really try and implement this "properly" from > the construction class in sage. This feels like the first big blocker. > > A "concrete" example of why we need this is when writing down the two > points at infinity for the real model. These are not "points" on the > current curve because the projective model is different and causes a range > of issues. > > *Constructing the right classes* > > I think aside from maybe needing additional methods on the hyperelliptic > curve, once the projective model is right and points on the curve are well > defined for all cases. I do not have any intuition on whether the balanced > model will for example have issues with the p-Adic implementation as I have > no experience in this area. > > Using the language of > https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch10.pdf, the > "imaginary" or ramified model is what is currently well supported in sage. > Here we have only one point at infinity. For the split or "real" model, > this is what is sketched out in my own repo and what I want to address, > there are two distinct points at infinity. Proper representation of the > degree zero divisors needs more than (u, v) for unique representation. For > the inert model, where there are no points at infinity over the base ring, > I think we should simply reject all arithmetic and force the user to change > the curve model or work over a field extension. This is what Magma does. > > This leads me to the Jacobian. I believe we should have a > `Jacobian_ramified` and `Jacobian_split` class and `Jacobian_inert`, each > with their own efficient (or missing) arithmetic and representation (the > inert case simply has NotImplemented for arithmetic. The hyperelliptic > curve class should know the number of points at infinity and then select > this class without user input (so H.jacobian() does whatever the use > expects). > > This will end up being a fairly large refactoring of the current code and > I believe this will be hazardous work! > > *=== Backwards compatibility * > > This is where I am most worried. I am familiar with and probably capable > of working with the curves over finite fields and building sensible classes > which allow for efficient arithmetic for odd and even genus for the > ramified and split models, but I know there's a lot more maths than the > arithmetic of these divisors and I need to ensure everything which everyone > needs works in the same way while making all these changes. > > *=== Next steps* > > This feels like a relatively big reworking of a very old part of Sage and > I think it's important to do, but I want to make sure I don't waste effort > on doing something which causes more harm than good. > > My gut feeling is a small group of people with interest in this area take > some time to try and rewrite the support for hyperelliptic curves and their > Jacobians and try and build something which is strong enough to be > practically useful. This really feels like an area of Sage drastically > under featured compared to Magma and it's important to me to try and make > this as good as possible. > > I would love advice from the community on how best to deal with this. > > > > -- > You received this message because you are subscribed to the Google Groups > "sage-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-devel+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/sage-devel/cf40307c-9a26-40cd-bb55-fde6cd5688e2n%40googlegroups.com > <https://groups.google.com/d/msgid/sage-devel/cf40307c-9a26-40cd-bb55-fde6cd5688e2n%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAD0p0K4YCcCxto%3DONkHxDu19EJJrN0yEAojZLpkq6PcGCniVYA%40mail.gmail.com.
