Title: Irreducibility and r-th root finding over finite fields,
Abstract: 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
$\mathbb{F}_q$ of characteristic $p$ (equivalently, constructing the bigger
field $\mathbb{F}_{q^{r^e}}$). Both these problems have famous randomized
algorithms but the derandomization is an open question. We give some new
connections between these two problems and their variants.
In 1897, Stickelberger proved that if a polynomial has an odd number of even
degree factors, then its discriminant is a quadratic nonresidue in the field.
We give an extension of Stickelberger's Lemma; we construct $r$-th nonresidues
from a polynomial $f$ for which there is a $d$, such that, $r|d$ and
$r\nmid\,$#(irreducible factor of $f(x)$ of degree $d$). Our theorem has the
following interesting consequences: (1) we can construct $\mathbb{F}_{q^m}$ in
deterministic poly(deg($f$),$m\log q$)-time if $m$ is an $r$-power and $f$ is
known; (2) we can find $r$-th roots in $\mathbb{F}_{p^m}$ in deterministic
poly($m\log p$)-time if $r$ is constant and $r|\gcd(m,p-1)$.
We also discuss a conjecture significantly weaker than the Generalized
Riemann hypothesis to get a deterministic poly-time algorithm for $r$-th root
finding.