Modular counting of rational points over finite fields
Let F-q be the finite field of q elements, where q = p(h). Let f(x) be a polynomial over F-q in n variables with m nonzero terms. Let N(f) denote the number of solutions of f(x) = 0 with coordinates in F-q. In this paper we give a deterministic algorithm which computes the reduction of N(f) modulo p(b) in O(n(8m)((h+b)p)) bit operations. This is singly exponential in each of the parameters {h, b, p}, answering affirmatively an open problem proposed by Gopalan, Guruswami, and Lipton.
p-adic modular counting of rational points sparse polynomials over finite fields stickelberger theorem gross-koblitz formula