Finding normal bases over finite fields with prescribed trace self-orthogonal relations

Normal bases and self-dual normal bases over finite fields have been found to be very useful in many fast arithmetic computations. It is well-known that there exists a self-dual normal basis of ${\mathbb{F}}_{2^n}$ over ${\mathbb{F}}_2$ if and only if $4\nmid n$. In this paper, we prove there exists a normal element $\alpha$ of ${\mathbb{F}}_{2^n}$ over ${\mathbb{F}}_2$ corresponding to a prescribed vector $a=(a_0,a_1,\mathrm{.}\mathrm{.}\mathrm{.},a_{n-1})\in {\mathbb{F}}_2^n$ such that $a_i={Tr}_{2^n\mathrm{\mid }2}({\alpha }^{1+2^i})$ for $0\le i\le n-1$, where $n$ is a 2-power or odd, if and only if the given vector $a$ is symmetric ($a_i=a_{n-i}$ for all $i,1\le i\le n-1$), and one of the following is true.

1. $n=2^s\ge 4$, $a_0=1$, $a_{n\mathrm{/}2}=0$, $\sum\limits_{1\leq i\leq n/2-1, (i,2)=1}a_i=1$;
2. $n$ is odd, $(\sum _{0\le i\le n-1}{a}_i{x}^i,x^n-1)=1$. Furthermore we give an algorithm to obtain normal elements corresponding to prescribed vectors in the above two cases. For a general positive integer $n$ with $4\mathrm{\mid }n$, some necessary conditions for a vector to be the corresponding vector of a normal element of ${\mathbb{F}}_{2^n}$ over ${\mathbb{F}}_2$ are given. And for all $n$ with $4\mathrm{\mid }n$, we prove that there exists a normal element of ${\mathbb{F}}_{2^n}$ over ${\mathbb{F}}_2$ such that the Hamming weight of its corresponding vector is 3, which is the lowest possible Hamming weight.