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

[Kwankyu Lee]

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

-- 
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/4dc27a25-cd0a-4d1e-be5b-e28a0cb8b32an%40googlegroups.com.

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

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

On Wed, Mar 6, 2024 at 11:55 AM Nils Bruin  wrote:

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

-- 
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/CAKLKTSQVthP93H3dqkK5UBdo_1xQi1iAVZjUP6oo-7YAo2QPaw%40mail.gmail.com.

[sage-devel] Re: Jupyter Lab Sage menu

[Marc Culler]

It would also be a good idea to open the javascript console and see if 
there are errors being reported around the time when the menu disappears.

- Marc

On Wednesday, March 6, 2024 at 8:20:00 PM UTC-6 Marc Culler wrote:

> Viviane,
>
> If you do a shift-reload (or whatever makes your browser clear its cache) 
> does that make the menu come back?
>
> - Marc
>
> On Wednesday, March 6, 2024 at 8:11:45 AM UTC-6 Viviane Pons wrote:
>
>> Dear all,
>>
>> I am working on a conda distribution of sage with jupyter lab. My conda 
>> environnement is only:
>>
>> name: jupyter-sage
>>
>> channels:
>> - conda-forge
>>
>> dependencies:
>> - jupyterlab
>> - sage
>>
>>
>> It works fine. I can launch it with "jupyter lab" or "sage 
>> --notebook=jupyterlab". I noticed that I had access to a bunch of tutorial 
>> links in the help menu (which is great!) but somehow this menu appears and 
>> disappears in ways that I don't understand at all. Do you know how / when 
>> this menu appears? 
>>
>> I have attached two screenshots. The same worksheet with Sage kernel is 
>> opened in both. In one case, I have the menu, in the other not
>>
>> (it looks like the menu appears when I first open the notebook but then, 
>> at some point, it just disappears and never comes back unless I restart 
>> jupyter lab entirely)
>>
>> Best
>>
>> Viviane
>>
>

-- 
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/0adb0579-fc20-4674-b388-cb822bef69cdn%40googlegroups.com.

[sage-devel] Re: Jupyter Lab Sage menu

[Marc Culler]

Viviane,

If you do a shift-reload (or whatever makes your browser clear its cache) 
does that make the menu come back?

- Marc

On Wednesday, March 6, 2024 at 8:11:45 AM UTC-6 Viviane Pons wrote:

> Dear all,
>
> I am working on a conda distribution of sage with jupyter lab. My conda 
> environnement is only:
>
> name: jupyter-sage
>
> channels:
> - conda-forge
>
> dependencies:
> - jupyterlab
> - sage
>
>
> It works fine. I can launch it with "jupyter lab" or "sage 
> --notebook=jupyterlab". I noticed that I had access to a bunch of tutorial 
> links in the help menu (which is great!) but somehow this menu appears and 
> disappears in ways that I don't understand at all. Do you know how / when 
> this menu appears? 
>
> I have attached two screenshots. The same worksheet with Sage kernel is 
> opened in both. In one case, I have the menu, in the other not
>
> (it looks like the menu appears when I first open the notebook but then, 
> at some point, it just disappears and never comes back unless I restart 
> jupyter lab entirely)
>
> Best
>
> Viviane
>

-- 
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/83d29836-9ca3-429c-9223-55b11451ce27n%40googlegroups.com.

Re: [sage-devel] Re: [Proposal] allow standard packages to be pip packages, reduce source tarball size

[Dima Pasechnik]

On Tue, Feb 20, 2024 at 1:57 AM Nathan Dunfield 
wrote:

> On Monday, February 19, 2024 at 3:08:54 PM UTC-6 John H Palmieri wrote,
> responding to Dima:
>
> You said: "The difference between wheel packages vs pip packages is that
> the latter don't require pre-fetched wheels, and absence of the need for
> package (micro)management." The implication is that changing the package
> management system is, maybe not part of this proposal, but a next step. In
> other words, I'm getting this impression from your words, not by other
> "certain parties."
>
> You said: "My proposal is in fact aimed at reducing the number of pinned
> Sage dependecies, drastically." (You have made similar comments elsewhere
> in this thread.) How does (1) accomplish this? Either I'm missing something
> or you have not spelled everything out in your proposal.
>
> You said '"Allow" does not mean "Make all of the", it should be obvious.'
>
> "Allow" does not cause any changes to happen drastically. So what exactly
> are you proposing to accomplish these drastic changes? If you have a
> roadmap in mind, it would be helpful if you described it.
>
>
> My understanding is that allowing standard packages to be pip packages
> could greatly reduce the number of pinned Sage dependencies for two reasons:
>
> 1) a build-from-source or wheel package must explicitly pin its version,
> but, more importantly,
>
> 2) a pip package is allowed to install additional dependencies of PyPI
> that are not recorded anywhere in the Sage repo.
>
> A simple example is pytest.  Here it is as an optional pip package:
>
> https://github.com/sagemath/sage/tree/develop/build/pkgs/pytest
>
> To be upgraded to a standard package, under the current policy would need
> to be turned into a "wheel package" requires adding its dependencies like
> so:
>
> https://github.com/sagemath/sage/pull/37301
>
> Here, pytest has just a few dependencies, but jupyterlab has more like 50
> when you include dependencies of dependencies.
>
> 
>
> Personally, I think the current system of having everything pinned and
> explicitly recorded is the right choice, being more stable in my experience
> with other projects.
>

the experience of Sage macOS app is that it's better to leave Sage's
jupyterlab (with its ~193 packages) totally aside, and use the undiluted
upstream jupyterlab instead, see
https://github.com/sagemath/sage/issues/37533#issuecomment-1981375822




> In any event, switching to a pip package for e.g. jupterlab doesn't affect
> the final size or complexity of Sage as installed, just how many moving
> pieces there appear to be if you look in "sage/build/pkgs".
>
> Best,
>
> Nathan
>
> --
> 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/f81b8284-cb48-44fe-a3f7-158be2438335n%40googlegroups.com
> 
> .
>

-- 
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/CAAWYfq2mMSU%3DjcjL%3DqJc69%3DGQ2pNDZt4FDVaJ%3Db%2Bb3N8gj72ww%40mail.gmail.com.

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

[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! 

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

Re: [sage-devel] Jupyter Lab Sage menu

[Dima Pasechnik]

Recent versions (10.3.*) of Sage have jupyterlab included,
so it's a bit hard to tell what exactly is going
on without seeing versions, etc.
Conda seems to provide sage 10.2.

It could be that installation of jupyterlab on top of
sage breaks something in the environment.

Using 10.3.rc2 might be a better way.


On Wed, Mar 6, 2024 at 2:11 PM Viviane Pons  wrote:

> Dear all,
>
> I am working on a conda distribution of sage with jupyter lab. My conda
> environnement is only:
>
> name: jupyter-sage
>
> channels:
> - conda-forge
>
> dependencies:
> - jupyterlab
> - sage
>
>
> It works fine. I can launch it with "jupyter lab" or "sage
> --notebook=jupyterlab". I noticed that I had access to a bunch of tutorial
> links in the help menu (which is great!) but somehow this menu appears and
> disappears in ways that I don't understand at all. Do you know how / when
> this menu appears?
>
> I have attached two screenshots. The same worksheet with Sage kernel is
> opened in both. In one case, I have the menu, in the other not
>
> (it looks like the menu appears when I first open the notebook but then,
> at some point, it just disappears and never comes back unless I restart
> jupyter lab entirely)
>
> Best
>
> Viviane
>
> --
> 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/CAPAYYh6W7XRuFrjb0xBABO3%3DmayqKrLnNZH6CSXVDgNUhr9CCQ%40mail.gmail.com
> 
> .
>

-- 
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/CAAWYfq11f8zhNmN%3DXpWa6WEgMQjTqPxoO2eA1bJkgqT4FsNDug%40mail.gmail.com.

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

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

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 sketc

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

[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

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 capa

Re: [sage-devel] sensational bug!

[Giacomo Pope]

This was also something I saw 
in: https://github.com/sagemath/sage/issues/37455 and I haven't been able 
to locally reproduce it either.

On Wednesday, March 6, 2024 at 12:18:51 PM UTC dmo...@deductivepress.ca 
wrote:

> I think this is issue 
> #35715  on the sagemath 
> github. So I think the discussion should go there.
>
> On Wednesday, March 6, 2024 at 6:53:04 AM UTC-5 Martin R wrote:
>
>> It is not my machine, just the bot, see the link above.
>>
>> On Wednesday 6 March 2024 at 12:42:19 UTC+1 Dima Pasechnik wrote:
>>
>>> Not confirmed here, either. We need more details about the machine, the 
>>> OS, the setup, etc.
>>>
>>> Is it reproducible, i.e. if you repeat this command, does it fail again?
>>>
>>> Dima
>>>
>>> On Wed, Mar 6, 2024 at 9:47 AM 'Martin R' via sage-devel <
>>> sage-...@googlegroups.com> wrote:
>>>
 On 
 https://github.com/sagemath/sage/actions/runs/8168335359/job/22330264302?pr=37545

 I see

 sage -t --long --random-seed=286735480429121101562228604801325644303 
 src/sage/rings/tests.py 
 ** 
 Error: Failed example:: Got: Random testing has revealed a problem in 
 test_karatsuba_multiplication 
 Please report this bug! You may be the first 
 person in the world to have seen this problem. 
 Please include this random seed in your bug report: 
 Random seed: 305806809989734915896642073966608392384 
 ValueError('Multiplication failed') 
 test_karatsuba_multiplication(QQbar, 3, 3, numtests=2) # long time, 
 needs sage.rings.number_field 
 Expected nothing 
 Got: 
 Random testing has revealed a problem in test_karatsuba_multiplication 
 Please report this bug! You may be the first 
 person in the world to have seen this problem. 
 Please include this random seed in your bug report: 
 Random seed: 305806809989734915896642073966608392384 
 ValueError('Multiplication failed') 

 -- 
 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/522bab60-a7e7-47f4-8d17-2c8ce329b85dn%40googlegroups.com
  
 
 .

>>>

-- 
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/be384c9a-c5b4-40e7-97d2-a518a60ef756n%40googlegroups.com.

[sage-devel] 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. = 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 relati

Re: [sage-devel] sensational bug!

[dmo...@deductivepress.ca]

I think this is issue #35715 
 on the sagemath github. So 
I think the discussion should go there.

On Wednesday, March 6, 2024 at 6:53:04 AM UTC-5 Martin R wrote:

> It is not my machine, just the bot, see the link above.
>
> On Wednesday 6 March 2024 at 12:42:19 UTC+1 Dima Pasechnik wrote:
>
>> Not confirmed here, either. We need more details about the machine, the 
>> OS, the setup, etc.
>>
>> Is it reproducible, i.e. if you repeat this command, does it fail again?
>>
>> Dima
>>
>> On Wed, Mar 6, 2024 at 9:47 AM 'Martin R' via sage-devel <
>> sage-...@googlegroups.com> wrote:
>>
>>> On 
>>> https://github.com/sagemath/sage/actions/runs/8168335359/job/22330264302?pr=37545
>>>
>>> I see
>>>
>>> sage -t --long --random-seed=286735480429121101562228604801325644303 
>>> src/sage/rings/tests.py 
>>> ** 
>>> Error: Failed example:: Got: Random testing has revealed a problem in 
>>> test_karatsuba_multiplication 
>>> Please report this bug! You may be the first 
>>> person in the world to have seen this problem. 
>>> Please include this random seed in your bug report: 
>>> Random seed: 305806809989734915896642073966608392384 
>>> ValueError('Multiplication failed') 
>>> test_karatsuba_multiplication(QQbar, 3, 3, numtests=2) # long time, 
>>> needs sage.rings.number_field 
>>> Expected nothing 
>>> Got: 
>>> Random testing has revealed a problem in test_karatsuba_multiplication 
>>> Please report this bug! You may be the first 
>>> person in the world to have seen this problem. 
>>> Please include this random seed in your bug report: 
>>> Random seed: 305806809989734915896642073966608392384 
>>> ValueError('Multiplication failed') 
>>>
>>> -- 
>>> 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/522bab60-a7e7-47f4-8d17-2c8ce329b85dn%40googlegroups.com
>>>  
>>> 
>>> .
>>>
>>

-- 
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/6345ae43-33da-4e1e-8f17-e14e2fc6d6bdn%40googlegroups.com.

Re: [sage-devel] sensational bug!

['Martin R' via sage-devel]

It is not my machine, just the bot, see the link above.

On Wednesday 6 March 2024 at 12:42:19 UTC+1 Dima Pasechnik wrote:

> Not confirmed here, either. We need more details about the machine, the 
> OS, the setup, etc.
>
> Is it reproducible, i.e. if you repeat this command, does it fail again?
>
> Dima
>
> On Wed, Mar 6, 2024 at 9:47 AM 'Martin R' via sage-devel <
> sage-...@googlegroups.com> wrote:
>
>> On 
>> https://github.com/sagemath/sage/actions/runs/8168335359/job/22330264302?pr=37545
>>
>> I see
>>
>> sage -t --long --random-seed=286735480429121101562228604801325644303 
>> src/sage/rings/tests.py 
>> ** 
>> Error: Failed example:: Got: Random testing has revealed a problem in 
>> test_karatsuba_multiplication 
>> Please report this bug! You may be the first 
>> person in the world to have seen this problem. 
>> Please include this random seed in your bug report: 
>> Random seed: 305806809989734915896642073966608392384 
>> ValueError('Multiplication failed') 
>> test_karatsuba_multiplication(QQbar, 3, 3, numtests=2) # long time, needs 
>> sage.rings.number_field 
>> Expected nothing 
>> Got: 
>> Random testing has revealed a problem in test_karatsuba_multiplication 
>> Please report this bug! You may be the first 
>> person in the world to have seen this problem. 
>> Please include this random seed in your bug report: 
>> Random seed: 305806809989734915896642073966608392384 
>> ValueError('Multiplication failed') 
>>
>> -- 
>> 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/522bab60-a7e7-47f4-8d17-2c8ce329b85dn%40googlegroups.com
>>  
>> 
>> .
>>
>

-- 
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/1cf13440-57cd-44d1-9be5-d01da08fd266n%40googlegroups.com.

Re: [sage-devel] sensational bug!

[Dima Pasechnik]

Not confirmed here, either. We need more details about the machine, the OS,
the setup, etc.

Is it reproducible, i.e. if you repeat this command, does it fail again?

Dima

On Wed, Mar 6, 2024 at 9:47 AM 'Martin R' via sage-devel <
sage-devel@googlegroups.com> wrote:

> On
> https://github.com/sagemath/sage/actions/runs/8168335359/job/22330264302?pr=37545
>
> I see
>
> sage -t --long --random-seed=286735480429121101562228604801325644303
> src/sage/rings/tests.py
> **
> Error: Failed example:: Got: Random testing has revealed a problem in
> test_karatsuba_multiplication
> Please report this bug! You may be the first
> person in the world to have seen this problem.
> Please include this random seed in your bug report:
> Random seed: 305806809989734915896642073966608392384
> ValueError('Multiplication failed')
> test_karatsuba_multiplication(QQbar, 3, 3, numtests=2) # long time, needs
> sage.rings.number_field
> Expected nothing
> Got:
> Random testing has revealed a problem in test_karatsuba_multiplication
> Please report this bug! You may be the first
> person in the world to have seen this problem.
> Please include this random seed in your bug report:
> Random seed: 305806809989734915896642073966608392384
> ValueError('Multiplication failed')
>
> --
> 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/522bab60-a7e7-47f4-8d17-2c8ce329b85dn%40googlegroups.com
> 
> .
>

-- 
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/CAAWYfq0kBnPtj-eeJ9RkbQwMcmo7hAJC%3D16DVvhUtOpnq5r%2BeQ%40mail.gmail.com.

Re: [sage-devel] Re: sensational bug!

[Salvatore Stella]

I can't reproduce it either:
on a Intel(R) Core(TM) i7-6900K CPU machine with 64Gb of RAM  running gentoo 
and sage 10.3.beta0

S.

--
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/ZehOaOPRRdEvgnfV%40bunion.

[sage-devel] Re: sensational bug!

[Frédéric Chapoton]

Indeed, interesting.

but *not confirmed* on my machine (Intel(R) Core(TM) i5-4690 on Linux 
ubuntu 22.04.4 LTS)

Frédéric
Le mercredi 6 mars 2024 à 10:47:36 UTC+1, Martin R a écrit :

> On 
> https://github.com/sagemath/sage/actions/runs/8168335359/job/22330264302?pr=37545
>
> I see
>
> sage -t --long --random-seed=286735480429121101562228604801325644303 
> src/sage/rings/tests.py 
> ** 
> Error: Failed example:: Got: Random testing has revealed a problem in 
> test_karatsuba_multiplication 
> Please report this bug! You may be the first 
> person in the world to have seen this problem. 
> Please include this random seed in your bug report: 
> Random seed: 305806809989734915896642073966608392384 
> ValueError('Multiplication failed') 
> test_karatsuba_multiplication(QQbar, 3, 3, numtests=2) # long time, needs 
> sage.rings.number_field 
> Expected nothing 
> Got: 
> Random testing has revealed a problem in test_karatsuba_multiplication 
> Please report this bug! You may be the first 
> person in the world to have seen this problem. 
> Please include this random seed in your bug report: 
> Random seed: 305806809989734915896642073966608392384 
> ValueError('Multiplication failed')

-- 
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/7021ce25-f9a3-4c2e-a176-f109e9079d6an%40googlegroups.com.

[sage-devel] sensational bug!

['Martin R' via sage-devel]

On 
https://github.com/sagemath/sage/actions/runs/8168335359/job/22330264302?pr=37545

I see

sage -t --long --random-seed=286735480429121101562228604801325644303 
src/sage/rings/tests.py 
** 
Error: Failed example:: Got: Random testing has revealed a problem in 
test_karatsuba_multiplication 
Please report this bug! You may be the first 
person in the world to have seen this problem. 
Please include this random seed in your bug report: 
Random seed: 305806809989734915896642073966608392384 
ValueError('Multiplication failed') 
test_karatsuba_multiplication(QQbar, 3, 3, numtests=2) # long time, needs 
sage.rings.number_field 
Expected nothing 
Got: 
Random testing has revealed a problem in test_karatsuba_multiplication 
Please report this bug! You may be the first 
person in the world to have seen this problem. 
Please include this random seed in your bug report: 
Random seed: 305806809989734915896642073966608392384 
ValueError('Multiplication failed')

-- 
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/522bab60-a7e7-47f4-8d17-2c8ce329b85dn%40googlegroups.com.