On the complexity of powering in finite fields
On the complexity of powering in finite fields
复制标题
有限域供电的复杂性
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Swastik Kopparty
中科院分区：
文献类型：
--
作者：
Swastik Kopparty
我们研究了通过 F<sub>2</sub> 上的恒定深度算术电路（也称为 ACP）计算 F<sub>2<sup>n</sup></sub> 元素的 k<sup>th</sup> 次方的复杂性。我们的研究涵盖了基本算术运算的复杂性，例如计算 F<sub>2<sup>n</sup></sub> 元素的立方根和计算立方剩余性。我们的主要结果是这些问题需要指数尺寸的电路。
我们还得出了这些结果的强平均情况版本。例如，我们表明，F<sub>2</sub> 上的次指数大小、恒定深度的算术电路无法正确计算 F<sub>2<sup>n</sup></sub> 元素的超过 1/3 + o(1) 分数的立方余数符号。作为推论，我们推导出一个字符和界，表明 F<sub>2<sup>n</sup></sub> 上的三次留数字符与所有 d 次 n 变量 F<sub>2</sub> 多项式不相关（以自然的方式将其视为 F<sub>2<sup>n</sup></sub> 上的函数），为某些通用 ε > 0 提供 d l n<sup>ε</sup>。经典方法（基于 van der Corput 差分和 Weil 界限）仅针对 d l log(n) 显示这一点。
我们的证明重新审视了电路下界的经典 Razborov-Smolensky 方法，并在 F<sub>2<sup>n</sup></sub> 上的单变量多项式领域中执行了类似的方法。我们使用的工具来自 F<sub>2<sup>n</sup></sub> 和 F<sub>2</sub><sup>n</sup>。近年来，F<sub>2<sup>n</sup></sub> 和 F<sub>2</sub><sup>n</sup> 之间的相互作用在伪随机性、属性测试和编码理论的许多结果中发挥了重要作用。
We study the complexity of computing the k<sup>th</sup>-power of an element of F<sub>2<sup>n</sup></sub> by constant depth arithmetic circuits over F<sub>2</sub> (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<sub>2<sup>n</sup></sub>. 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<sub>2</sub> can correctly compute the cubic residue symbol for more than 1/3 + o(1) fraction of the elements of F<sub>2<sup>n</sup></sub>. As a corollary, we deduce a character sum bound showing that the cubic residue character over F<sub>2<sup>n</sup></sub> is uncorrelated with all degree-d n-variate F<sub>2</sub> polynomials (viewed as functions over F<sub>2<sup>n</sup></sub> in a natural way), provided d l n<sup>ε</sup> 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<sub>2<sup>n</sup></sub>. The tools we use come from both F<sub>2<sup>n</sup></sub> and F<sub>2</sub><sup>n</sup>. In recent years, this interplay between F<sub>2<sup>n</sup></sub> and F<sub>2</sub><sup>n</sup> has played an important role in many results in pseudorandomness, property testing and coding theory.