GCD of polynomials and Bezout matrices
Luca Gemignani · 1997
A new algorithm is presented for computing an integer polynomial similar to the GCD of two polynomials 7~(z) and v(z) E Z[z], deg (u(~)) = n 2 deg (v(z)).Our approach uses structured matrix computations involving Bezout matrices rather than Hankel matrices.In this way we reduce the computational costs showing that the new algorithm requires 0(n2) arithmetical operations or 0(rr4(log2 n + 12)) Boolean operations, where 1 = max{log(ll u(z) Ilm), log(ll u(x) Ilm)}. 1