Re: [sage-devel] Help and Advice | Arithmetic of Jacobians in the Split/Real Model is Broken
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, 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. = 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
Re: [sage-devel] Help and Advice | Arithmetic of Jacobians in the Split/Real Model is Broken
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, 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. = 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
[sage-devel] Help and Advice | Arithmetic of Jacobians in the Split/Real Model is Broken
*=== 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. = 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
