Electronic Colloquium on Computational Complexity
Login | Register | Classic Style

Reports tagged with finite field:
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 >>>

TR12-068 | 25th May 2012
Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena

Deterministic Polynomial Factoring and Association Schemes

The problem of finding a nontrivial factor of a polynomial $f(x)$ over a finite field $\mathbb{F}_q$ has many known efficient, but randomized, algorithms. The deterministic complexity of this problem is a famous open question even assuming the generalized Riemann hypothesis (GRH). In this work we improve the state of the ... more >>>

TR14-018 | 13th February 2014
Arnab Bhattacharyya

Polynomial decompositions in polynomial time

Fix a prime $p$. Given a positive integer $k$, a vector of positive integers ${\bf \Delta} = (\Delta_1, \Delta_2, \dots, \Delta_k)$ and a function $\Gamma: \mathbb{F}_p^k \to \F_p$, we say that a function $P: \mathbb{F}_p^n \to \mathbb{F}_p$ is $(k,{\bf \Delta},\Gamma)$-structured if there exist polynomials $P_1, P_2, \dots, P_k:\mathbb{F}_p^n \to \mathbb{F}_p$ ... more >>>

TR17-016 | 31st January 2017
Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena

Irreducibility and deterministic r-th root finding over finite fields

Constructing $r$-th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree $r^e$ (where $r$ is a prime) over a given finite field $\F_q$ of characteristic $p$ (equivalently, constructing the bigger field $\F_{q^{r^e}}$). Both these problems have famous randomized ... more >>>

ISSN 1433-8092 | Imprint