# GCD of polynomials and Bezout matrices

A new algorithm is presented for computing
an integer polynomial similar to the GCD of
two polynomials $u(x)$ and $v(x)$ $\in {\bf Z}[x]$, $\deg(u(x))=n\geq
\deg(v(x)) $. 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 $O(n^2)$ arithmetical
operations or $O(n^4(\log^2 n +l^2))$ Boolean operations,
where $l=\max
\{ \log(\parallel u(x) \parallel_{\infty}), \log(\parallel v(x)
\parallel_{\infty})\}$.