Details:
Title  New fast euclidean algorithms  Author(s)  MarieFrançoise Roy, Sidi Mohamed Sedjelmaci  Type  Article in Journal  Abstract  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_2 d )^2 ) , where d is the degree of the polynomials, similarly to Schönhage (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 / 2 M ( d ) + O ( d ) ) log_2 d where d is the degree of the polynomials in the nondefective case (when degrees drop one by one), and ( 21 M ( d ) + O ( d ) ) log_2 d + O ( M ( d ) ) in the general case, improving the complexity bounds (respectively ( 10 M ( d ) + O ( d ) ) log 2 d and ( 24 M ( d ) + O ( d ) ) log_2 d + O ( 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.  Keywords  Fast algorithms, Greatest common divisor (gcd), Halfgreatest common divisor (halfgcd), Quotient boot, Complexity  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S0747717112001216 
Language  English  Journal  Journal of Symbolic Computation  Volume  50  Number  0  Pages  208  226  Year  2013  Edition  0  Translation 
No  Refereed 
No 
