Richard B. Kreckel wrote:
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.
If a and b are coprime, then there is a unique solution if g of degree less than deg(a)+deg(b), the normalization is done by euclidean division of u and v by b and a
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. :-)
It's probably done by solving the same Bezout identity for a few primes and reconstruction by Chinese remaindering, just like for (in my opinion fastest, except for small inputs) modular GCD algorithm. The main difference being that the upper bound for coefficients in u and v is larger (bounded by the resultant of a and v instead of by the Landau-Mignotte bound). If my recollection is correct, von zur Gathen & Gerhard book describes a modular Bezout algorithm. Bernard Parisse