# 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.

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