Fwd: [sage-devel] Help and Advice | Arithmetic of Jacobians in the Split/Real Model is Broken

[John Cremona]

---------- Forwarded message ---------
From: Giacomo Pope <giaco...@gmail.com>
Date: Wed, 6 Mar 2024, 12:52
Subject: [sage-devel] Help and Advice | Arithmetic of Jacobians in the Split/Real Model is Broken
To: sage-devel <sage-...@googlegroups.com>

=== 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+...@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.