Quadratic Probabilistic Algorithms for Normal Bases

Mark Giesbrecht, Armin Jamshidpey, Éric Schost

It is well known that for any finite Galois extension field $K/F$, with Galois group $G=\mathrm{Gal}(K/F)$, there exists an element $\alpha \in K$ whose orbit $G\cdot \alpha$ forms an $F$-ba…