Opened 8 years ago

# xgcd is badly named on non PID domains

Reported by: vdelecroix major basic arithmetic jdemeyer, bruno N/A

### Description

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.

### comment:1 Changed 8 years ago by vdelecroix

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.

### comment:2 follow-up:  3 Changed 8 years ago by bruno

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.

### comment:3 in reply to:  2 ; follow-up:  4 Changed 8 years ago by jdemeyer

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

### comment:4 in reply to:  3 Changed 8 years ago by bruno

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