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
AN - SCOPUS:77953024766
VL - 45
SP - 879
EP - 886
JO - Journal of Symbolic Computation
JF - Journal of Symbolic Computation
SN - 0747-7171
IS - 8
ER -