Vol. 1, No. 1, 2013

Download this article
Download this article For screen
For printing
Recent Volumes
1: ANTS X
The Open Book Series
About the Series
Ethics Statement
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 Fpm[x] of degree d over the finite field Fpm, one can view it as a map from Fpm to Fpm, 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 (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.

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