Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



TR05-087 | 9th August 2005 00:00

Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two



We study the complexity of arithmetic in finite fields of characteristic two, $\F_{2^n}$.
We concentrate on the following two problems:

Iterated Multiplication: Given $\alpha_1, \alpha_2,..., \alpha_t \in \F_{2^n}$, compute $\alpha_1 \cdot \alpha_2 \cdots \alpha_t \in \F_{2^n}$.

Exponentiation: Given $\alpha \in \F_{2^n}$ and a $t$-bit integer $k$, compute $\alpha^k \in \F_{2^n}$.

First, we consider the explicit realization of the field $\F_{2^n}$ as $\F_2[x]/(x^{2 \cdot 3^l} + x^{3^l} + 1) \simeq \F_{2^n}$, where $n = 2 \cdot 3^l$.
In this setting, we exhibit Dlogtime-uniform poly(n,t)-size TC^0 circuits computing exponentiation.
To the
best of our knowledge, prior to this work it was not even known
how to compute exponentiation in logarithmic space, i.e. space
$O(\log (n + t))$, over any finite field of size $2^{\Omega(n)}$.
We also exhibit, for every $\eps > 0$, Dlogtime-uniform poly (n,2^{t^\eps})-size AC^0[mod 2] circuits computing iterated multiplication and exponentiation, which we prove is optimal.

Second, we consider arbitrary realizations of $\F_{2^n}$ as
$\F_2[x]/(f(x))$, for an irreducible $f(x) \in \F_2[x]$ that is given as part of the input. In this setting, we
exhibit, for every $\eps > 0$, Dlogtime-uniform poly (n,2^{t^\eps})-size AC^0[mod 2] circuits
computing iterated multiplication, which
is again tight. We also exhibit Dlogtime-uniform poly(n,2^t)-size AC^0[mod 2] circuits
computing exponentiation.

Our results over $\F_2[x]/(x^{2 \cdot 3^l} + x^{3^l} + 1)$ have several consequences:

We prove that Dlogtime-uniform TC^0 equals the class AE of functions computable by certain arithmetic expressions. This answers a question raised by Frandsen, Valence and Barrington (Mathematical Systems Theory '94).
We also show how certain optimal constructions of $k$-wise independent and $\eps$-biased
generators are explicitly computable in Dlogtime-uniform AC^0[mod 2] and TC^0. This addresses a question raised by Gutfreund and Viola (RANDOM '04).

ISSN 1433-8092 | Imprint