ECCC-Report TR05-087https://eccc.weizmann.ac.il/report/2005/087Comments and Revisions published for TR05-087en-usMon, 15 Aug 2005 19:28:18 +0300
Paper TR05-087
| Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two |
Alexander Healy,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2005/087We 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).
Mon, 15 Aug 2005 19:28:18 +0300https://eccc.weizmann.ac.il/report/2005/087