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 >>>