TR05-087 Authors: Alexander Healy, Emanuele Viola

Publication: 15th August 2005 19:28

Downloads: 2172

Keywords:

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).