#### Vol. 1, No. 1, 2013

 Recent Volumes 5: Gauge Theory and Low-Dimensional Topology 4: ANTS XIV 3: Hillman: Poincaré Duality 2: ANTS XIII 1: ANTS X
 The Open Book Series All Volumes About the Series Ethics Statement Purchase Printed Copies Author Index ISSN (electronic): 2329-907X ISSN (print): 2329-9061 MSP Books and Monographs Other MSP Publications
Counting value sets: algorithm and complexity

### Qi Cheng, Joshua E. Hill and Daqing Wan

Vol. 1 (2013), No. 1, 235–248
##### Abstract

Let $p$ be a prime. Given a polynomial in ${\mathbb{F}}_{{p}^{m}}\left[x\right]$ of degree $d$ over the finite field ${\mathbb{F}}_{{p}^{m}}$, one can view it as a map from ${\mathbb{F}}_{{p}^{m}}$ to ${\mathbb{F}}_{{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 ${\left(pmd\right)}^{O\left(d\right)}$. 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=\mathfrak{2}$, and $m$ is allowed to vary, or when the polynomial is given as a straight-line program, $m=\mathfrak{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.

##### Keywords
finite field, polynomial value set cardinality, point counting, polynomial time, randomized polynomial time, RP-reduction, NP-hard, \#P-hard, straight-line program, sparse polynomial, subset sum problem
##### Mathematical Subject Classification 2010
Primary: 11Y16
Secondary: 11Y40, 68Q17
##### Milestones
Published: 14 November 2013
##### Authors
 Qi Cheng School of Computer Science The University of Oklahoma Norman, OK 73019 United States Joshua E. Hill Department of Mathematics University of California, Irvine Irvine, CA 92697 United States Daqing Wan Department of Mathematics University of California, Irvine Irvine, CA 92697 United States