Skip to Main content Skip to Navigation
New interface
Journal articles

Approximate GCD of several univariate polynomials, small degree perturbations

Mohamed Elkadi 1, 2 André Galligo 1, 2 Ba Thang Luu 2, 3 
2 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis (1965 - 2019), CNRS - Centre National de la Recherche Scientifique : UMR6621
Abstract : We consider the following computational problem, posed by von zur Gathen et al. [18]: given a family of generic univariate polynomials f := (f0 , ..., fs ), construct an algorithm to find polynomial purtubbations u :=(u0 , ..., us ) with "small" degrees such that the GCD (greater common divisor) of the perturbed family f + u has a "large" degree. In this paper, we propose an algorithm which solves this problem in polynomial time under a generic condition generalizing the normal degree sequence used in [18] for the case s = 1.
Document type :
Journal articles
Complete list of metadata
Contributor : Ba Thang Luu Connect in order to contact the contributor
Submitted on : Friday, October 22, 2010 - 11:09:31 AM
Last modification on : Thursday, August 4, 2022 - 5:05:32 PM

Links full text




Mohamed Elkadi, André Galligo, Ba Thang Luu. Approximate GCD of several univariate polynomials, small degree perturbations. Journal of Symbolic Computation, 2012, 47 (4), pp.410-421. ⟨10.1016/j.jsc.2011.09.005⟩. ⟨inria-00528634⟩



Record views