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
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
${\left(pmd\right)}^{O\left(d\right)}$.
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=\mathfrak{2}$,
and
$m$ is
allowed to vary, or when the polynomial is given as a straightline program,
$m=\mathfrak{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.
