Approximate polynomial gcd: Small degree and small height perturbations

Joachim von zur Gathen; Maurice Mignotte; Igor E. Shparlinski

doi:10.1016/j.jsc.2010.04.001

Approximate polynomial gcd

Small degree and small height perturbations

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

^*Corresponding author for this work

Department of Computing

Research output: Contribution to journal › Article

10 Citations (Scopus)

Abstract

We consider the following computational problem: we are given two coprime univariate polynomials f₀ and f₁ 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 language	English
Pages (from-to)	879-886
Number of pages	8
Journal	Journal of Symbolic Computation
Volume	45
Issue number	8
DOIs	https://doi.org/10.1016/j.jsc.2010.04.001
Publication status	Published - Aug 2010

Access to Document

10.1016/j.jsc.2010.04.001

Link to publication in Scopus

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

Cite this

@article{120370716dc348a09d07596cc201cda3,

title = "Approximate polynomial gcd: Small degree and small height perturbations",

abstract = "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{"}.",

author = "{von zur Gathen}, Joachim and Maurice Mignotte and Shparlinski, {Igor E.}",

year = "2010",

month = "8",

doi = "10.1016/j.jsc.2010.04.001",

language = "English",

volume = "45",

pages = "879--886",

journal = "Journal of Symbolic Computation",

issn = "0747-7171",

publisher = "ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD",

number = "8",

}

TY - JOUR

T1 - Approximate polynomial gcd

T2 - Small degree and small height perturbations

AU - von zur Gathen, Joachim

AU - Mignotte, Maurice

AU - Shparlinski, Igor E.

PY - 2010/8

Y1 - 2010/8

N2 - 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".

AB - 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".

UR - http://www.scopus.com/inward/record.url?scp=77953024766&partnerID=8YFLogxK

U2 - 10.1016/j.jsc.2010.04.001

DO - 10.1016/j.jsc.2010.04.001

M3 - Article

VL - 45

SP - 879

EP - 886

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

SN - 0747-7171

IS - 8

ER -