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

Abstract

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,...,a_{n-1})\in {\mathbb{F}}_2^n$ such that $a_i={Tr}_{2^n|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/2}=0$, $\sum _{1\le i\le 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|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|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.