Mathematics – Number Theory
Scientific paper
2011-11-04
Mathematics
Number Theory
Scientific paper
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 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 in \cite{Kaltofen03,KaltofenKo05}.
Cheng Qing-Qi
Hill Joshua E.
Wan Daqing
No associations
LandOfFree
Counting Value Sets: Algorithm and Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Counting Value Sets: Algorithm and Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting Value Sets: Algorithm and Complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-101706