New structure theorem for subresultants

We give a new structure theorem for subresultants precising their gap struc ture and derive from it a new algorithm for computing them. If d is a bound on the degrees and tau a bound on the bit size of the miners extracted fro m Sylvester matrix, our algorithm has O(d(2)) arithmetic operations and siz e of intermediate computations 2 tau. The key idea is to precise the relati ons between the successive Sylvester matrix of A and B on one hand and of A and XB an the other hand, using the notion of G-remainder that we introduc e. We also compare our new algorithm with another algorithm with the same c haracteristics which appeared in Ducos (2000). (C) 2000 Academic Press.