Tenth Algorithmic Number Theory Symposium ANTS-X University of California, San Diego July 9 – 13, 2012 Tenth Algorithmic Number Theory Symposium (ANTS-X) July 9 – 13, 2012

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 non-trivial 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 non-trivial 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=2, and m is allowed to vary, or when the polynomial is given as a straight-line program, m=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.

Files available: paper (PDF)