Maple: gcdex CLN: xgcd Pari: bezout Mma: ExtendedGCD MuPAD: gcdex Singular: extgcd Lidia: xgcd
@Ralf: Can you say anything about the uniqueness of the cofactors computed by your xgcd function? I mean, when you have g==u*a+v*b you also have g==(u+b)*v+(v-a)*b and so on. With integers it is trivial to normalize u and v, e.g. to the smallest possible absolute values.
You mean g==(u+b)*a+(v-a)*b, no I can't say anything about this, the literature is mostly about integers, and I have not the background to tackle it. BTW the Magma manual says Ch. 44 UNIVARIATE POLYNOMIAL RINGS 187 Xgcd(f, g) XGCD(f, g) The extended greatest common divisor of polynomials f and g in a univariate polynomial ring P : the function returns polynomials c, a and b in P such that c is the GCD f and g (as defined in the function GreatestCommonDivisor), and a * f + b * g = c. The coefficient ring must be a field. Since the GCD c is unique, the multipliers a and b are unique if f and g are both non-zero. For polynomials over the rational field, a modular algorithm due to Allan Steel(unpublished) is used; over other fields the basic Euclidean algorithm is used. So there is another algorithm to ponder... ralf