xgcd is badly named on non PID domains

[videlec]

Over non PID domains, the method xgcd might not (and can not in general) return the gcd as its first argument

sage: x = polygen(ZZ)
sage: (x+2).gcd(x+4)  # no common factor but...
1
sage: (x+2).xgcd(x+4) # ... the ideal (x+2, x+4) is not principal
(2, -1, 1)

See this sage-devel thread where it was suggested to change the method name to pseudo_xgcd or _resultant_xgcd.

See also #17671 that fix some compatibility issues for gcd/xgcd over PID.

CC: @jdemeyer @bgrenet

Component: basic arithmetic

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

[videlec]

comment:1

Wikipedia is formal about the definition of xgcd. But there is a mention of

as + bt = Res(a,b)

in the section Polynomial extended Euclidean algorithm. See also the page on Bézout identity

magma defines xgcd only for univariate polynomials over fields or residue class ring with prime modulus.

[bgrenet]

comment:2

Let me repeat and extend as a comment my remarks on sage-devel, concerning the "literature":

• In almost all books in which I've checked, the extended Euclidean algorithm is only defined for polynomials over fields, and not over rings. This books include

  • Modern Computer Algebra (von zur Gathen and Gerhard);
  • The Art of Computer Programming: Semi-Numerical Algorithms (Knuth);
  • A Computational Introduction to Number Theory and Algebra (Shoup);
  • Fundamental problems in algorithmic algebra (Yap).
    The exception is in
  • A course in computational number theory (Cohen)
    where there is a mention (as a remark and and exercise) of the extended Euclidean Algorithm in the case of polynomials over UFDs, and the algorithm is suppose to return g*r, s and t where g is the GCD and r the resultant, and s and t satisfy g*r = s*a+t*b for inputs a and b.

• For softwares and libraries (inputs are two univariate polynomials a and b over the integers):

  • Flint: fmpz_poly_xgcd computes r, s and t where r=res(a,b) and r=s*a+t*b;
  • NTL: idem Flint;
  • Mathemagix: the xgcd-like function returns an error;
  • Maple17: the function gcdex works as if a and b were defined over the rational numbers;
  • Mathematica (? tested via WolframAlpha): idem Maple17.

Now for my opinion:

• My preferred solution is the one chosen by Flint and NTL, keeping the name xgcd;
• If the consensus is to change the name, I would be greatly in favor of a name beginning with xgcd_... for completion considerations.

[jdemeyer]

comment:3

Replying to @bgrenet:

• My preferred solution is the one chosen by Flint and NTL, keeping the name xgcd;

FLINT does not use the name xgcd, it uses the name fmpz_poly_xgcd. This may look like nitpicking, but it's really not. The FLINT call is explicit that it's for fmpz_poly: polynomials over ZZ. When you use the generic xgcd name to mean both the "real" xgcd and the "fake" xgcd-times-resultant depending on the input, that's confusing.

[bgrenet]

comment:4

Replying to @jdemeyer:

Replying to @bgrenet:

• My preferred solution is the one chosen by Flint and NTL, keeping the name xgcd;

FLINT does not use the name xgcd, it uses the name fmpz_poly_xgcd. This may look like nitpicking, but it's really not. The FLINT call is explicit that it's for fmpz_poly: polynomials over ZZ. When you use the generic xgcd name to mean both the "real" xgcd and the "fake" xgcd-times-resultant depending on the input, that's confusing.

In Sage you have the object-oriented syntax object.method() while in Flint there is some kind of naming convention type_function(). And you have fmpz_poly_xgcd exactly in the same way as you have fmpz_xgcd or fmpq_poly_xgcd, so one could argue, in the same way as you argue for the xgcd function in Sage, that a user expects these functions to implement the same mathematical function in the three cases. I am not sure (even if you think so) that the situation in Sage is much more confusing than the situation in Flint. Actually, I do not think it is really confusing in any case.