Subquadratic-time algorithms for normal bases (Q2040602)

In a finite Galois extension \(K/F\) with Galois group \(G=\mathrm{Gal}(K/F)\), an element \(\alpha\in K\) is called \textit{normal} if its Galois orbit \(\alpha^G\) forms an \(L\)-basis of \(K\). Under the assumption that \(K\) is represented \(K=L(\xi)\) with a power basis \(1,\xi,\xi^2,\ldots\), and the elements of \(G\) are given through their action on \(\xi\), and that \(G\) is abelian or metacyclic, the authors give a Monte-Carlo algorithm to test whether a particular element \(\alpha\in K\) is normal. This algorithm runs in time \(\tilde{\mathcal O}(n^e)\) for \(e<1.99\). (The soft-O notation \(\tilde{\mathcal O}\) leaves out logarithmic factors.) The concrete value for \(e\) is \(3/4\cdot\omega(3/4)\), where \(\omega(3/4)\) stems from the cost of multiplying by a \(n\times n^{3/4}\) matrix. This extends their prior result [\textit{M. Giesbrecht} et al., in: Proceedings of the 44th international symposium on symbolic and algebraic computation, ISSAC '19, Beijing, China, July 15--18, 2019. New York, NY: Association for Computing Machinery (ACM), 179--186 (2019; Zbl 1467.11124)] from abelian to metabelian Galois groups. They also show that they can perform basis conversion between the power basis and \(\alpha^G\) in the same (Monte-Carlo) complexity.