On the complexity of powering in finite fields
Swastik Kopparty · 2011
We study the complexity of computing the k th-power of an element of F2n by constant depth arithmetic circuits over F2 (also known as AC 0 (⊕)). Our study encompasses the complexity of basic arithmetic operations such as computing cube-root and computing cubic-residuosity of elements of F2n. 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 F2 can correctly compute the cubic residue symbol for more than 1/3 + o(1) fraction of the elements of F2n. As a corollary, we deduce a character sum bound showing that the cubic residue character over F2n is uncorrelated with all degree-d n-variate F2 polynomials (viewed as functions over F2n in a natural way), provided d ≪ n ɛ for some universal ɛ> 0. Classical methods (based on van der Corput differencing and the Weil bounds) show this only for d ≪ 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 F2n. The tools we use come from both F2n and Fn2. In recent years, this interplay between F2n and Fn2 has played an important role in many results in pseudorandomness, property testing and coding theory.