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 F2nF2n over F2F2 if and only if 4∤n4∤n. In this paper, we prove that there exists a normal element α   of F2nF2n over F2F2 corresponding to a prescribed vector a=(a0,a1,…,an−1)∈F2n such that ai=Tr2n|2(α1+2i)ai=Tr2n|2(α1+2i) for 0⩽i⩽n−10⩽i⩽n−1, where n is a 2-power or odd, if and only if the given vector a   is symmetric (ai=an−iai=an−i for all i  , 1⩽i⩽n−11⩽i⩽n−1), and one of the following is true.(1)n=2s⩾4n=2s⩾4, a0=1a0=1, an/2=0an/2=0, ∑1⩽i⩽n/2−1,(i,2)=1ai=1;(2)n   is odd, (∑0⩽i⩽n−1aixi,xn−1)=1(∑0⩽i⩽n−1aixi,xn−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|n4|n, some necessary conditions for a vector to be the corresponding vector of a normal element of F2nF2n over F2F2 are given. And for all n   with 4|n4|n, we prove that there exists a normal element of F2nF2n over F2F2 such that the Hamming weight of its corresponding vector is 3, which is the lowest possible Hamming weight.