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. On Wednesday, March 6, 2024 at 1:52:26 PM UTC John Cremona wrote: > 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, <giaco...@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+...@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/cb91ee61-3c06-4ecd-b5ac-7adcc93345a1n%40googlegroups.com.
