Fast Deterministic Normal Bases and Circulant Polynomial Determinants

Let $\mathsf{E}=\mathbb{F}_q[x]/(Γ)$ describe an algebraic extension of a finite field $\mathbb{F}_q$, where $q$ is a prime power and $Γ\in\mathbb{F}_q[x]$ is monic and irreducible of degree $n$. We give a deterministic algorithm that finds $β\in \mathsf{E}$ whose conjugates $β,β^q,\ldots,β^{q^{n-1}