Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ARITHMETIC EXPRESSION:
Reports tagged with arithmetic expression:
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