Beating brute force for systems of polynomial equations over finite fields

We consider the problem of solving systems of multivariate polynomial equations of degree k over a finite field. For every integer k ≥ 2 and finite field 𝔽q where q = pd for a prime p, we give, to the best of our knowledge, the first algorithms that achieve an exponential speedup over the brute force O(qn) time algorithm in the worst case. We present two algorithms, a randomized algorithm with running time qn+o(n) · q−n/O(k) time if q ≤ 24ekd, and [EQUATION] otherwise, where e = 2.718... is Napier's constant, and a deterministic algorithm for counting solutions with running time qn+o(n) ·q−n/O(kq6/7d). For the important special case of quadratic equations in 𝔽2, our randomized algorithm has running time O(20.8765n).