zbMATH — the first resource for mathematics

New fast Euclidean algorithms. (English) Zbl 1303.11130
Summary: We give new simple algorithms for the fast computation of the quotient boot and the gcd of two polynomials, and obtain a complexity \(O(d(\log_2d)^2)\), where \(d\) is the degree of the polynomials, similarly to [A. Schönhage, Acta Inf. 1, 139–144 (1971; Zbl 0223.68008)], [R. T. Moenck, Proc. 5th ann. ACM Symp. Theor. Comput., Austin 1973, 142–151 (1973; Zbl 0306.68027)]. More precisely, denoting by \(M(d)\) the cost of a fast multiplication of polynomials of degree \(d\), we reach the complexity \((\tfrac 92 M(d) + O(d)) \log_2 d\) where \(d\) is the degree of the polynomials in the non-defective case (when degrees drop one by one), and \((21M(d) + O(d)) \log_2 d + O(M(d))\) in the general case, improving the complexity bounds (respectively \((10M(d)+O(d)) \log_2 d\) and \((24M(d)+O(d)) \log_2 d+O(M(d)))\)) previously known for these problems (J. von zur Gathen and J. Gerhard, Modern computer algebra. Cambridge: Cambridge University Press (1999; Zbl 0936.11069), 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.

11Y16 Number-theoretic algorithms; complexity
68W30 Symbolic computation and algebraic computation
13P05 Polynomials, factorization in commutative rings
Full Text: DOI