On Taking r-th Roots without r-th Nonresidues over Finite Fields and Its Applications

Tsz-Wo Sze

We first show a deterministic algorithm for taking $r$-th roots over $\F_q$ without being given any $r$-th nonresidue, where $\F_q$ is a finite field with $q$ elements and $r$ is a…