New fast euclidean algorithms

We give new simple algorithms for the fast computation of the quotient boot and the gcd of two polynomials, and obtain a complexity , where d is the degree of the polynomials, similarly to Schönhage (1971), Moenck (1973). More precisely, denoting by M(d) the cost of a fast multiplication of polynomials of degree d, we reach the complexity where d is the degree of the polynomials in the non-defective case (when degrees drop one by one), and in the general case, improving the complexity bounds (respectively and ) previously known for these problems (von zur Gathen and Gerhard, 1999, see Exercise 11.7).We hope that the simple character of our algorithms will make it easier to use fast algorithms in practice for these problems.