Approximate polynomial gcd: Small degree and small height perturbations

Joachim von zur Gathen*, Maurice Mignotte, Igor E. Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


We consider the following computational problem: we are given two coprime univariate polynomials f0 and f1 over a ring R and want to find whether after a small perturbation we can achieve a large gcd. We solve this problem in polynomial time for two notions of "large" (and "small"): large degree (when R=F is an arbitrary field, in the generic case when f0 and f1 have a so-called normal degree sequence), and large height (when R=Z). Our work adds to the existing notions of "approximate gcd".

Original languageEnglish
Pages (from-to)879-886
Number of pages8
JournalJournal of Symbolic Computation
Issue number8
Publication statusPublished - Aug 2010


Dive into the research topics of 'Approximate polynomial gcd: Small degree and small height perturbations'. Together they form a unique fingerprint.

Cite this