CJTCS Volume 2016 Article 10

Volume 2016

Article 10

Published by the Department of Computer Science, The University of Chicago.

Circuit Complexity of Powering in Fields of Odd Characteristic

Arkadev Chattopadhyay
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road, Mumbai 400005, INDIA;
arkadev DOT c AT tifr DOT res DOT in

Frederic Green
Department of Mathematics and Computer Science
Clark University, Worcester, MA 01610;
fgreen AT clarku DOT edu

Howard Straubing
Computer Science Department
Boston College, Chestnut Hill, MA 02467;
straubin AT cs DOT bc DOT edu

August 3, 2016

Abstract

By a careful analysis of the proofs of Kopparty in fields of characteristic 2, we show that the problem of powering in $\mathbb{F}_{p^n}$ requires $\mathrm{ACC}(p)$ circuits of exponential size (in $n$), for any fixed prime $p > 2$. Similar bounds hold for quadratic residuosity. As a corollary, we obtain non-trivial bounds for exponential sums that express the correlation between the quadratic character of $\mathbb{F}_{p^n}$ and $n$-variate polynomials over $\mathbb{F}_p$ of degree up to $n^{\epsilon}$ for some $0 < \epsilon < 1$.

The article: PDF (284 KB)
Source material: ZIP (84 KB)
BibTeX entry for this article (324 bytes)

Submitted November 10, 2014, revised March 28, 2016, and in final form July 28, 2016, published August 3, 2016.

DOI: 10.4086/cjtcs.2016.010