Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleNew fast euclidean algorithms
Author(s) Marie-Françoise Roy, Sidi Mohamed Sedjelmaci
TypeArticle in Journal
AbstractWe 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 non-defective 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.
KeywordsFast algorithms, Greatest common divisor (gcd), Half-greatest common divisor (half-gcd), Quotient boot, Complexity
ISSN0747-7171
URL http://www.sciencedirect.com/science/article/pii/S0747717112001216
LanguageEnglish
JournalJournal of Symbolic Computation
Volume50
Number0
Pages208 - 226
Year2013
Edition0
Translation No
Refereed No
Webmaster