Hi! On Wed, 17 Nov 2004, Ralf Stephan wrote:
@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,
If that turns out to be undetermined, it should just be documented as such.
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.
As it stands, that last sentence is not correct. To see that, just drop any two elements of any integral domain in a and b and try shifting them according to above equation. Maybe there is some other way to "normalize" u and v to the most simple form? Or maybe that is a non-issue for some reason we don't see?
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...
...not unless Allan shares some of his insights with us. :-) Regards -richy. -- Richard B. Kreckel <http://www.ginac.de/~kreckel/>