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 0 (d(log(2)d)(2)), where d is the degree of the polynomials, similarly to Schonhage (1971), Moenck (1973). More precisely, denoting by M(d) the cost of a fast multiplication of polynomials of degree d, we reach the complexity (9/2M(d) + 0(d))log2d where d is the degree of the polynomials in the non-defective case (when degrees drop one by one), and (21M(d) + 0(d))log2d + 0(M(d)) in the general case, improving the complexity bounds (respectively (10M(d) + 0(d)) log(2) d and (24M(d) + 0(d))log2d + 0(M(d))) 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. (C) 2012 Elsevier B.V. All rights reserved.
quotient boot complexity fast algorithms greatest common divisor (gcd) half-greatest common divisor (half-gcd)