Counting value sets: algorithm and complexity
Qi Cheng, Joshua Hill, Daqing Wan · The Open Book Series · 2013
Let p be a prime.Given a polynomial in ކ p m Œx of degree d over the finite field ކ p m , one can view it as a map from ކ p m to ކ p m , and examine the image of this map, also known as the value set of the polynomial.In this paper, we present the first nontrivial algorithm and the first complexity result on explicitly computing the cardinality of this value set.We show an elementary connection between this cardinality and the number of points on a family of varieties in affine space.We then apply Lauder and Wan's p-adic point-counting algorithm to count these points, resulting in a nontrivial algorithm for calculating the cardinality of the value set.The running time of our algorithm is .pmd/ O.d / .In particular, this is a polynomial-time algorithm for fixed d if p is reasonably small.We also show that the problem is #P-hard when the polynomial is given in a sparse representation, p D 2, and m is allowed to vary, or when the polynomial is given as a straight-line program, m D 1 and p is allowed to vary.Additionally, we prove that it is NP-hard to decide whether a polynomial represented by a straight-line program has a root in a prime-order finite field, thus resolving an open problem proposed by Kaltofen and Koiran.