New fast euclidean algorithms

Marie-Françoise Roy (1) , Sidi Mohamed Sedjelmaci (2)

1 IRMAR - Institut de Recherche Mathématique de Rennes
2 LIPN - Laboratoire d'Informatique de Paris-Nord

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

Mots clés: Fast algorithms; Greatest common divisor (gcd); Half-greatest common divisor (half-gcd); Quotient boot; Complexity

Domaines: Calcul formel [cs.SC]

Marie-Françoise Roy, Sidi Mohamed Sedjelmaci. New fast euclidean algorithms. Journal of Symbolic Computation, 2013, 50, pp.208-226. ⟨10.1016/j.jsc.2012.06.003⟩. ⟨hal-00785099⟩