Detecting lacunary perfect powers and computing their roots (Q650838)

The paper deals with the problem of determining whenever a polynomial \(f\) is equal to the \(r\)-th power of a polynomial \(h\). The authors provide algorithms to solve this problem, based on the lacunary representation of a polynomial, so that their method turns out to be efficient mainly for sparse polynomials. Initially they propose a Monte-Carlo algorithm which determines if a polynomial \(f\) can be a perfect power and, if so, it determines also which is the power. Then they provide an algorithm that starting from a polynomial \(f\), known to be a \(r\)-th perfect power, computes the polynomial \(h\) such that \(f = h^r\). The results are obtained firstly considering univariate polynomials in \(\mathbb{Z}[x]\) or \(\mathbb{F}_q[x]\) (for large characteristic) and then extended to the case of multivariate polynomials.