On the Euclidean Algorithm of Polynomials

Yuichi FUTA  Koh-ichi NAGAO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E84-A   No.5   pp.1261-1265
Publication Date: 2001/05/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
Euclidean algorithm,  polynomial,  Karatsuba's algorithm,  

Full Text: PDF(147.8KB)>>
Buy this Article




Summary: 
In order to compute gcd of polynomials, the Euclidean algorithm is used. We estimate the complexities of known Euclidean algorithms. Further, we propose a heuristic Euclidean algorithm. This is faster than ordinary methods under some special conditions by the use of the recurrent Karatsuba multiplication.