GCD, XGCD for polynomial rings with templating

[sagetrac-spancratz]

GCD and XGCD methods should return monic greatest common divisors. However, at the moment these two methods in the template file sage/rings/polynomial/polynomial_template.pxi prevent this by enforcing that gcd(a,0) == a and gcd(0,b) == b.

I suggest that the code for these two methods in the template file should only refer to the corresponding celement_foo methods of the actual implementation. This way, all the logic is in the celement_foo methods, rather than being split between the two levels.

The patch for this should touch the template file as well as the two linkage files for GF2X and zmod polynomials.

CC: @rwst @jpflori

Component: algebra

Author: Sebastian Pancratz

Issue created by migration from https://trac.sagemath.org/ticket/6941

[malb]

comment:1

Attachment: trac_6941_monicgcd.patch.gz

The patch looks good, applies cleanly and doctests pass. However, do we really need to mimic the old behaviour?

[sagetrac-spancratz]

comment:2

Replying to @malb:

The patch looks good, applies cleanly and doctests pass. However, do we really need to mimic the old behaviour?

I assume you are referring to the hyperelliptic curves part? Yes, I think so. Otherwise, some doctests fail. I haven't tried to fully understand the mathematics of that part, but it seems to depend on the assumption gcd(a,0) == a.

Sebastian

[malb]

comment:3

Maybe we can ask the person who wrote that code?

[robertwb]

comment:6

If we need to mimic the old xgcd behavior, it would be much better to abstract that out into its own function with a docstring and some tests.