Subquadratic-Time Algorithms for Normal Bases

Mark Giesbrecht, Armin Jamshidpey, Éric Schost

For any finite Galois field extension $\mathsf{K}/\mathsf{F}$, with Galois group $G=\mathrm{Gal}(\mathsf{K}/\mathsf{F})$, there exists an element $\alpha \in \mathsf{K}$ whose orbit $G…