[GiNaC-list] code: extended gcd

[bernard.parisse]

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