Computing low-degree factors of lacunary polynomials: a Newton-Puiseux approach

Abstract : We present a new algorithm for the computation of the irreducible factors of degree at most $d$, with multiplicity, of multivariate lacunary polynomials over fields of characteristic zero. The algorithm reduces this computation to the computation of irreducible factors of degree at most $d$ of univariate lacunary polynomials and to the factorization of low-degree multivariate polynomials. The reduction runs in time polynomial in the size of the input polynomial and in $d$. As a result, we obtain a new polynomial-time algorithm for the computation of low-degree factors, with multiplicity, of multivariate lacunary polynomials over number fields, but our method also gives partial results for other fields, such as the fields of $p$-adic numbers or for absolute or approximate factorization for instance. The core of our reduction uses the Newton polygon of the input polynomial, and its validity is based on the Newton-Puiseux expansion of roots of bivariate polynomials. In particular, we bound the valuation of $f(X,\phi)$ where $f$ is a lacunary polynomial and $\phi$ a Puiseux series whose vanishing polynomial has low degree.
Document type :
Conference papers
Complete list of metadatas

https://hal-polytechnique.archives-ouvertes.fr/hal-00936319
Contributor : Bruno Grenet <>
Submitted on : Friday, January 24, 2014 - 7:15:23 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:26 PM

Links full text

Identifiers

Collections

Citation

Bruno Grenet. Computing low-degree factors of lacunary polynomials: a Newton-Puiseux approach. 39th International Symposium on Symbolic and Algebraic Computation, Jul 2014, Kobe, Japan. p224-231, ⟨10.1145/2608628.2608649⟩. ⟨hal-00936319⟩

Share

Metrics

Record views

271