2014/12/31 by Bruno Grenet
Computer Science · Mathematics · #Algorithm #Bounded function #Coding theory and cryptography #Combinatorics #Cryptography and Residue Arithmetic #Degree (music) #Degree of a polynomial #Discrete mathematics #Factorization #Factorization of polynomials #Field (mathematics) #Lacunary function #Mathematical analysis #Mathematics #Matrix polynomial #Monic polynomial #Multivariate statistics #Polynomial #Polynomial and algebraic computation #Polytope #Pure mathematics #Square-free polynomial #Stable polynomial #Univariate #cs.CC #cs.DS #cs.SC
paper · pdf · doi:10.1016/j.jsc.2015.11.013
published as Journal of Symbolic Computation 75, pages 171-192, 2016 · 31 pages; Long version of arXiv:1401.4720 with simplified proofs
openalex publication_date 2015/11/05 · arxiv created 2016/01/29 · arxiv updated 2016/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
In this paper, we present a new method for computing bounded-degree factors of lacunary multivariate polynomials. In particular for polynomials over number fields, we give a new algorithm that takes as input a multivariate polynomial f in lacunary representation and a degree bound d and computes the irreducible factors of degree at most d of f in time polynomial in the lacunary size of f and in d. Our algorithm, which is valid for any field of zero characteristic, is based on a new gap theorem that enables reducing the problem to several instances of (a) the univariate case and (b) low-degree multivariate factorization. The reduction algorithms we propose are elementary in that they only manipulate the exponent vectors of the input polynomial. The proof of correctness and the complexity bounds rely on the Newton polytope of the polynomial, where the underlying valued field consists of Puiseux series in a single variable.