Help and Advice | Arithmetic of Jacobians in the Split/Real Model is Broken

[Giacomo Pope]

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

[John Cremona]

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

--
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.

[Giacomo Pope]

Thanks John.

From my minimal local testing I have at least that

- random sampling on the jacobian can find every point on the jacobian (there is a fast method using sums of J(P) for P on the curve, but this doesnt guarantee all elements of the jacobian are found)

- that multiplication by any random point by the order of the jacobian gives the zero element

- that every element has an order dividing the order of the jacobian computed using `order_from_multiple`

- that this seems to work for char 2 and odd char providing there are two points at infinity (base assumption).

- that the implementation of negation works as expected and for random points D - D is always zero

Now that these basic features are in place and we have addition, subtraction and multiplication by scalars, I want to make sure the functions are as simple as possible to aid with the integration into sage.

[Nils Bruin]

On Wednesday 6 March 2024 at 04:52:16 UTC-8 Giacomo Pope wrote:

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.

Tiny bit of feedback on the p-adic bit: as far as I know, things like Cantor's algorithm use euclidean division, wwhich is a big problem p-adically: coefficients may vanish unexpectedly and p-adically you cannot distinguish that from loss of precision. I think that's already a problem in the existing implementation and I think it will be in yours as well. So I think you can ignore p-adics to begin with. If you can get it working usefully and reliably for p-adic base fields as well then that's a real win!

[Zachary Scherr]

Just wanted to mention that I posted about something similar a few years ago here: https://groups.google.com/g/sage-support/c/j1Y9yuu-VuE/m/cA7N8iqCCAAJ.  At the time a trac ticket was opened, but I'm not sure about the status especially post the github migration.

--

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/f4de3410-1d9e-4cc7-b518-7471f6c1ecean%40googlegroups.com.

[Kwankyu Lee]

It's still here: https://github.com/sagemath/sage/issues/32024

[Sabrina Kunzweiler]

Thanks for mentioning the related discussion. We checked that in the new implementation in Giacomo's repository, this issue is solved.

In the example that was given in the chat, we obtain the following output:
```
sage: R.<x> = QQ[]
sage: f = 144*x^6 - 240*x^5 + 148*x^4 + 16*x^3 - 16*x^2 - 4*x + 1
sage: H = HyperellipticCurveNew(f)
sage: J = Jacobian(H)
sage: P = J(H([0,1]))-J(H([0,-1]))
sage: (5*P).is_zero()
False
sage: 5*P
(1, 0 : 2)
```
Here, this means $$ 5 P = (1:12:0) - (1:-12:0) $$ which coincides with the result from magma.

[Giacomo Pope]

As a small update, the repository now contains code to

- perform arithmetic for

  - the imaginary model (ramified, one point at infinity) for all cases

  - the real model (split, two points at infinity) for all cases

  - the real model (inert, zero points at infinity) for even genus

  Which allows us to do "as much" as Magma does for Jacobians of hyperellipticc curves from the perspective of arithmetic. 

My current "test" for the arithmetic is that D - D = 0 for all cases, that jacobian_order * D = zero and that order_from_multiple(D) works. If people have other ideas for tests, please let me know. Of course at the moment these tests are over finite fields but you can reasonable use other fields (as Sabrina's message shows) but I am less sure about how to do randomised testing here.

- We also have a function which can randomly (but not uniformly) sample elements of the Jacobian for all the cases.

- We can compute the order of the Jacobian from the frob. polynomial and using the arithmetic and in-build `order_from_multiple` then find the order of divisors

I think the next thing to do is to look at isomorphisms and maybe even isogenies (Richelot only for genus two perhaps?)

If you are interested in this area and want to contribute, then I think fleshing out the code in this repo will be easier during these early stages and once it feels complete we can look at replacing the current code in sagemath with this newer version.

[Kwankyu Lee]

On Friday, March 8, 2024 at 7:37:04 PM UTC+9 Giacomo Pope wrote:

As a small update, the repository now contains code to

- perform arithmetic for

  - the imaginary model (ramified, one point at infinity) for all cases

  - the real model (split, two points at infinity) for all cases

  - the real model (inert, zero points at infinity) for even genus

  Which allows us to do "as much" as Magma does for Jacobians of hyperellipticc curves from the perspective of arithmetic. 

My current "test" for the arithmetic is that D - D = 0 for all cases, that jacobian_order * D = zero and that order_from_multiple(D) works. If people have other ideas for tests, please let me know. Of course at the moment these tests are over finite fields but you can reasonable use other fields (as Sabrina's message shows) but I am less sure about how to do randomised testing here.

I just set https://github.com/sagemath/sage/pull/35467 to "needs review" status. The PR implements Jacobian arithmetic for general projective curves.

It is slow compared with Jacobian arithmetic using Mumford representation, but could be used to crosscheck the computations.

[Giacomo Pope]

Thank you for linking this and I agree this is a great way to cross-compare the work we have been doing. I am not an expert in this area so I am not sure I should do a full review but I'm happy to look over it if this helps.

As a small update on this work, I now have 

class HyperellipticCurveSmoothModel(AlgebraicScheme_subscheme_toric)

So this new class builds on top of AlgebraicScheme_subscheme_toric and the smooth projective model is built using a toric variety. The points on the curve are currently SchemeMorphism_point_toric_field, potentially I will need to make a child class of these if methods on the points themselves are required.

With the working arithmetic and this new inheritance my work is now going to be the rather slow and painful rewrite of all hyperelliptic methods from the current implementation to ensure everything works on the smooth degree model.

[David Roe]

There is also this old trac ticket about implementing fast arithmetic in genus 2 Jacobians, which never made it into Sage.  I've CCed Mike Jabobson, who worked on it.

David

--

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/7f646c6d-bd0b-452d-a730-30144415f590n%40googlegroups.com.

[Giacomo Pope]

Thanks David, there's a bunch of nice things we could do for genus two in various cases which would be worth including. The inert case, where all degree zero divisors (except the identity element) have u with degree 2 would probably allow something particularly nice. 

As another update I have done a fairly brutish refactoring of the proof of concept code to follow the design decisions of the previous implementation. https://github.com/GiacomoPope/HyperellipticCurves

Hyperelliptic curves are created from a dynamic class constructor on top of the AlgebraicScheme_subscheme_toric class (before this was a curve over the plane projective curves)

A generic class offers most features, but other classes will cover the case of finite fields, rational fields and padic fields

The Jacobian is a small class built on top of `jacobian_generic` which is built from the curve

The set of rational points of the Jacobian is built on top of SchemeHomSet and the elements (divisors) are morphisms built on top of SchemeMorphism

I will do my best to clean up and refactor code to the standard of code which is included into Sage now, but I would love to know any feedback advice on whether this structure is still the one to use. The older version of this code dates back to the beginning of Sage so it's very possible we have new ideas of how things should be done and if we're doing the work or rewriting the whole set of classes I may as well do a good job.

Giacomo

[Nils Bruin]

One thing that may deserve a cursory check is the overhead involved in inheriting from AlgebraicScheme_subscheme_toric class . Some parent structures are optimized for prolonged use *after* creation and may do a lot of caching/precomputation. There may be scenarios where one wants to construct *lots* of hyperelliptic curves (for instance, when computing reductions of hyperelliptic curves mod lots of primes). An expensive parent may then add undue overhead. In that case it may be better to spin off the functionality required into a "lightweight" structure that gets wrapped in the expensive, full functionality parent. After all, for core algorithms a hyperelliptic curve is just a 3*g+5 length sequence of ring/field elements: the coefficients of the defining equation.

There are of course also odd genus hyperelliptic curves that cover a genus 0 curve that is not isomorphic to a P^1, but computing in their Jacobians has its own problems, so you should probably not try to include them in your current design.

One thing that may be worthwhile: hyperelliptic curves do inherit some interesting functionality from plane curves (particularly via their affine patch) in the form of "riemann_surface". It may be worth keeping that, even if the particular code there could be expanded to work much more efficiently on hyperelliptic curves.

[Giacomo Pope]

Thanks so much for the context

Oh interesting. In this case I wonder whether we should work on and include a new class (maybe something as simple as a WeightedProjectiveSpace and a curve from this) mirroring the implementation for the plane curves. Alternatively I could go into the old plane curve code and write these useful functions specifically for the hyperelliptic curves (and here even gain that these algorithms can be optimised). For example, I already had to include a `dimension()` method on the curve to properly compute the Jacobian. Potentially AlgebraicScheme_subscheme_toric is indeed the wrong inheritance

[Giacomo Pope]

Back again with more class questions and general advice help

While getting all the old sage code into this new project, I realised there are places where we really rely on the underlying curve classes. One example is that we need

```

def dimension():

    return 1

```

To avoid some crashes, but more generally we also need `rational_points()` which lives all the way inside `Algebraic_scheme`. There's also a whole bunch of other things...

I started exploring more and I found `Curve_generic` which we can create with the data I already have:

```

sage: H = HyperellipticCurveSmoothModel(x^5 + x + 1)

sage: C = Curve_generic(H._projective_model.ambient_space(), H._projective_model.defining_polynomials())
sage: type(C)
<class 'sage.schemes.curves.curve.Curve_generic_with_category'>
sage: C
Generic Curve over Rational Field defined by -X^5*Z - X*Z^5 - Z^6 + Y^2
sage: C.ambient_space()
2-d toric variety covered by 3 affine patches

```

this gets us some of the way and I think is an OK starting point, but then things like asking for the curve crash for weighted projective space:

```

sage: Curve(H)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
.
TypeError: ambient space neither affine nor projective

```

and calls to things like C.rational_points() have more issues

```

sage: C.rational_points(bounds=2)
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
.
AttributeError: 'SchemeHomset_points_subscheme_toric_field_with_category' object has no attribute 'points'

```

Which just goes to show that these toric varieties are a little underdeveloped.

Something which might be really nice would be 

```

class WeightedProjectiveCurve(Curve_generic, AlgebraicScheme_subscheme_toric):

```

Intended to mirror the similar:

```

class ProjectiveCurve(Curve_generic, AlgebraicScheme_subscheme_projective):

```

This could then be the class which is inherited by the Hyperelliptic curve class and we could aim for better coverage here.

Any opinions on this? Any idea of people who might have thought about or made progress in this area?

Otherwise, the project continues. Functions for finite fields are all working, generic functions mostly and the padic functions are a WIP as we need to adapt to the fact we have different points at infinity (and I dont know how to properly handle the case when there's two (yet)).

Finally, looking at the rational_points() method itself, this is something people have at least considered:

```

        .. TODO::

            Implement Stoll's model in weighted projective space to
            resolve singularities and find two points (1 : 1 : 0) and
            (-1 : 1 : 0) at infinity.

```

[Giacomo Pope]

To make discussion on this point easier, I have made a GitHub issue: https://github.com/sagemath/sage/issues/37626

For progress on this code, we have all doctests passing from the old implementation except:

- we cannot define toric varieties over rings, so we can't have hyperelliptic curves over rings

- we cannot use the current rational_points method from algebraic_schemes due to missing methods in the homset of toric varieties

We are also working on pairings as well as isomorphisms on top of supporting all older features.

[Giacomo Pope]

Hey all, 

Wanted to bump this as we have done a bunch of work (slowly, over the months) at rewriting the whole hyperelliptic curve class to work over the smooth model:

https://github.com/GiacomoPope/HyperellipticCurves

The plan we have is to introduce a new directory

/schemes/hyperelliptic_curves_smooth_model 

with this new curve and have `HyperellipticCurveSmoothModel` be a new object exported (to work along side HyperellipticCurve)

I was writing here for a few questions

1. This will be a very large PR, is this generally an OK thing to do?

2. I believe it might be easier to make changes to this code in the current repo before merging to sage, so if people reading this want to contribute then we're discussing the code in the Sage zulip and we'd be happy for more people to look at and improve the code

3. If people object to: /schemes/hyperelliptic_curves_smooth_model then I would love to know of a better/different solution

Any advice would be appreciated -- I really want to find a way to get this new code into sage as I think having working arithmetic of Jac(C) for many more cases is desirable and will allow for some really nice additional functionality for hyperelliptic curves into sagemath

[Nils Bruin]

On Wednesday 9 October 2024 at 09:31:45 UTC-7 giaco...@gmail.com wrote:

1. This will be a very large PR, is this generally an OK thing to do?

Generally smaller PRs are easier to get merged, but I'm not sure if merging n PRs of size m takes more or less time than merging one PR of size n*m. If you can easily get some parts split off to merge as smaller PRs you'd be able to get a "foot in the door" by getting those merged. But if that really doesn't make sense, you could also prefer to stick with the large PR. Especially with a large PR, I would recommend to design it such that you DON'T change things outside of it. That way, the scope of your large PR remains limited. That makes review easier.

Further tie-in into the rest of the infrastructure, where you do need to touch files outside your primary domain is probably better done in follow-up PRs. You could already make them, but they would have a dependence on the main initial PR.

 

2. I believe it might be easier to make changes to this code in the current repo before merging to sage, so if people reading this want to contribute then we're discussing the code in the Sage zulip and we'd be happy for more people to look at and improve the code

You can try that, but I would expect that deviating from the normal flow of things (which is: a PR on sagemath) would slow down the review process. It's already hard to find people for that, and now you want them to follow a custom procedure? You may be able to get the best of both worlds by some git magic where you keep your own repo overlayed with the pull request. I don't know if a tree can live in two repositories at once or if there are ways to conveniently synchronize two subtrees of two distinct projects.

 

Mathematical comment: you'll get problems for mumford representation on nonsplit imaginary hyperelliptic curves of odd genus. You want an odd degree divisor to serve as a base of representing all classes and such a thing might simply not exist. Indeed, there may be points on the Jacobian that do not allow a representing divisor over the base field.

[Giacomo Pope]

OK -- I'll do my best to break things down into the most manageable sizes to give this the best chance.

As for the maths/arithmetic, what we have coded gets Sage to the same point as Magma, although with a different representation. 

In our implementation, we follow the paper: https://eprint.iacr.org/2008/265. Generically, a divisor is represented by (u, v : n) where (u, v) are the Mumford coordinates of the divisor and n is the coefficient of \infty_+. As we can always deduce the coefficient m of \infty_- from deg(u) and n, this is omitted. Additionally, when the curve itself is ramified or inert then we can also deduce n and we instead represent elements as (u, v).

Unless I am mistaken, we can handle arithmetic with a unique representation of all divisors of Jac(C) for all cases with the exception of inert curves with odd genus. In this case, we raise an error when trying to perform arithmetic on this case. I believe this is what Magma does to.

[Giacomo Pope]

Replying here in case readers of this thread are interested -- a **not really finished** PR has now been made to Sage with a lot of the changes we describe above. I kind of want people to look at it and give rough opinions to move the project forward to the point where we can merge it and start improving it

https://github.com/sagemath/sage/pull/39161