Algorithms to construct normal bases of cyclic number fields (Q1801579)

The authors give two algorithms for obtaining a normal basis of a cyclic extension \(K\) of degree \(d\) of the rational numbers \(\mathbb{Q}\). The more explicit algorithm works as follows: given an element \(\vartheta\) so that \(K=\mathbb{Q}[\vartheta]\), one constructs a certain set \(S\subseteq\mathbb{Q}\) of cardinality \(\leq 2d^ 3\); then for any \(r\) in \(\mathbb{Q}\setminus S\) there is some \(N\) so that one of the elements \(\{\vartheta+r, (\vartheta+r)^ 2,\dots, (\vartheta+r)^ N\}\) generates a normal basis. Here \(N\) is an explicit function of \(d\) which grows like \(\exp(\exp(\exp d))\). The proof uses ideas of \textit{S. A. Stepanov} and \textit{E. E. Shparlinskij} [Mat. Sb. 180, 1067-1072 (1989; Zbl 0694.12014)] in constructing normal bases of finite extensions of finite fields, and of \textit{H. P. Schlickewei} [Acta Math. 170, No. 2, 151-180 (1993; Zbl 0789.11012)] on the number of zeros of certain linear recurrence sequences.