FAST PARALLEL COMPUTATION OF THE POLYNOMIAL REMAINDER SEQUENCE VIA BEZOUT AND HANKEL-MATRICES

If u(x) and upsilon(x) are polynomials of degree n and m, respectively, m < n, all the coefficients of the polynomials generated by the Euclidean scheme applied to u(x) and upsilon(x) can be computed by using O (log(3) n) parallel arithmetic steps and n(2)/log n processors over any held of characteristic O supporting FFT (Fast Fourier Transform). If the field does not support FFT the number of processors is increased by a factor of log log n; if the field does not allow division by n ! the number of processors is increased by a factor of n. This result is obtained by reducing the Euclidean scheme to computing the block triangular factorization of the Bezout matrix associated with u(x) and upsilon(x). This approach is also extended to the evaluation of polynomial gcd (greatest common divisor) over any field of constants in O (log(2)n steps with the same number of processors.