New fast euclidean algorithms

作者：Roy Marie Francoise^*; Sedjelmaci Sidi Mohamed

来源：Journal of Symbolic Computation, 2013, 50: 208-226.

DOI：10.1016/j.jsc.2012.06.003

• Fast algorithms
• Greatest common divisor (gcd)
• Half-greatest common divisor (half-gcd)
• Quotient boot
• Complexity

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). %26lt;br%26gt;We hope that the simple character of our algorithms will make it easier to use fast algorithms in practice for these problems.

• 出版日期2013-3