An algorithm for the construction of a normal basis (Q1306693)

Let \(L/K\) be a degree \(n\) Galois extension of fields of characteristic non zero. Let \(G=\{s_1,\ldots,s_n\}\) be its Galois group. The author gives an iterative algorithm to construct an element \(y\in L\) such that \((s_1(y),\ldots,s_n(y))\) is a basis of the \(K\)-vector space \(L\), called a normal basis of \(L/K\). The existence of such an element follows from the fact that \(D= \det(\sum_{j=1}^n s_ks_l(x_j)Z_j)_{k,l}\) is a non-zero polynomial. If \(z\) is not a zero of \(D\), then it defines a normal basis. The author starts with the investigation of the complexity of the algorithm which looks for a normal basis by trial and error using the standard method of above. The main purpose of the paper under review is to give an iterative method to find a normal basis. This algorithm requires \(O(n^4)\) multiplications in the ground field. By the normal basis theorem \(L\) is a \(K[G]\)-module which is isomorphic to \(K[G]\). Now the algorithm iteratively finds an element \(v\) such that \(K[G]\rightarrow L:\alpha\mapsto \alpha v\) is an isomorphism.