Computing low-degree factors of lacunary polynomials: a Newton-Puiseux approach - Archive ouverte HAL Access content directly
Conference Papers Year : 2014

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

(1)
1
Bruno Grenet

#### 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.

#### Domains

Computer Science [cs] Symbolic Computation [cs.SC]

### Dates and versions

hal-00936319 , version 1 (24-01-2014)

### Identifiers

• HAL Id : hal-00936319 , version 1
• ARXIV :
• DOI :

### Cite

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⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

113 View