Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > K-WISE INDEPENDENT GENERATOR:
Reports tagged with k-wise independent generator:
TR05-087 | 9th August 2005
Alexander Healy, Emanuele Viola

#### 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}$.

... more >>>

ISSN 1433-8092 | Imprint