The computation of polynomial greatest common divisors over an algebraic number field

Lars Langemyr, Scott McCallum

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

Abstract

We present an algorithm for computing the greatest common divisor of two polynomials over an algebraic number field. We obtain a better computing time bound for this algorithm than for previously published algorithms solving the same problem. We have also performed empirical run time tests which have confirmed this. Our motivation for seeking the algorithm of the present paper stems from our interest in the cylindrical algebraic decomposition (cad) algorithm (Collins [3], Arnon et al. [1]). The cad algorithm makes essential use of algebraic polynomial gcd computations, which often dominate the cost of the algorithm. Our algorithm is a generalization of the modular algorithm developed by Brown.

Original languageEnglish
Title of host publicationEurocal 1987 - European Conference on Computer Algebra , Proceedings
EditorsJames H. Davenport
PublisherSpringer-VDI-Verlag GmbH & Co. KG
Pages298-299
Number of pages2
ISBN (Print)9783540515173
DOIs
Publication statusPublished - 1 Jan 1989
Externally publishedYes
Event6th International Conference on Computer Algebra, EUROCAL 1987 - Leipzig, Germany
Duration: 2 Jun 19875 Jun 1987

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume378 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Conference on Computer Algebra, EUROCAL 1987
CountryGermany
CityLeipzig
Period2/06/875/06/87

Fingerprint Dive into the research topics of 'The computation of polynomial greatest common divisors over an algebraic number field'. Together they form a unique fingerprint.

Cite this