On the complexity of powering in finite fields

We study the complexity of computing the k^th-power of an element of F_2n by constant depth arithmetic circuits over F₂ (also known as ACP). Our study encompasses the complexity of basic arithmetic operations such as computing cube-root and computing cubic-residuosity of elements of F_2n. Our main result is that these problems require exponential size circuits. We also derive strong average-case versions of these results. For example, we show that no subexponential-size, constant-depth, arithmetic circuit over F₂ can correctly compute the cubic residue symbol for more than 1/3 + o(1) fraction of the elements of F_2n. As a corollary, we deduce a character sum bound showing that the cubic residue character over F_2n is uncorrelated with all degree-d n-variate F ₂ polynomials (viewed as functions over F_2n in a natural way), provided d l n^∈ for some universal ∈ > 0. Classical methods (based on van der Corput differencing and the Weil bounds) show this only for d l log(n). Our proof revisits the classical Razborov-Smolensky method for circuit lower bounds, and executes an analogue of it in the land of univariate polynomials over F_2n. The tools we use come from both F_2n and F₂ⁿ. In recent years, this interplay between F_2n and F₂ⁿ has played an important role in many results in pseudorandomness, property testing and coding theory.