Self-conjugate normal bases of finite fields (Q1326013)

Let \(p\) be a prime number and \(q\) a powr of \(p\). The system of elements \(\vartheta_ 0, \dots, \vartheta_{n-1}\) is called a self-conjugate normal basis of \(\mathbb{F}_{q^ n}\) over \(\mathbb{F}_ q\) if it is a normal basis and satisfies the relations \(\text{tr} (\vartheta_ i \vartheta_ j)= \delta_{ij}\), \(0\leq i,j\leq n-1\), where tr is the trace of elements of \(\mathbb{F}_{q^ n}\) in \(\mathbb{F}_ q\) and \(\delta_{ij}\) is the Kronecker symbol. It is shown in the present paper that if \(p=2\) then \(\mathbb{F}_{q^ n}\) has a self-conjugate normal basis over \(\mathbb{F}_ q\) if and only if \(n\) is not divisible by 4. For a broad class of finite fields there is given a formula that expresses an element of \(\mathbb{F}_{q^ n}\) generating a self-conjugate normal basis over \(\mathbb{F}_ q\). The complexity of the calculation of the irreducible polynomial corresponding to the basis constructed in this way is polynomially bounded in \(n\). The result can be used to obtain self-conjugate normal bases of \(\mathbb{F}_{2^ n}\) over \(\mathbb{F}_ 2\) for all \(n\leq 6\cdot 10^ 9\) such that \(4, 1093, 3511 \nmid n\). Remark that the translation contains several disturbing misprints: e.g. p. 85. 1.1. \(\omega_{n-1}\) instead of \(\omega_{n_ 1-1}\), p. 86. 1.1. \((\;)\) instead of 0, p. 88, 1.16. \(r^{r-1}-1\) instead of \(2^{r- 1} -1\).