Tenth Algorithmic Number Theory Symposium ANTSX

Counting value sets: algorithm and complexity
Qi Cheng, Joshua E. Hill, and Daqing Wan
Abstract: Let p be a prime. Given a polynomial in F_{p^m}[x] of degree d over the finite field F_{p^m}, one can view it as a map from F_{p^m} to F_{p^m}, and examine the image of this map, also known as the value set. 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 padic pointcounting 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 polynomialtime algorithm for fixed d if p is reasonably small. We also show that the problem is #Phard when the polynomial is given in a sparse representation, p=2, and m is allowed to vary, or when the polynomial is given as a straightline program, m=1 and p is allowed to vary. Additionally, we prove that it is NPhard to decide whether a polynomial represented by a straightline program has a root in a primeorder finite field, thus resolving an open problem proposed by Kaltofen and Koiran.
Files available: paper (PDF)
XHTML 1.1 valid, CSS valid