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

Original · EN

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 F₂ₙ over F₂ if and only if 4 n. In this paper, we prove there exists a normal element α of F₂ₙ over F₂ corresponding to a prescribed vector a=(a₀,a₁,...,aₙ₋₁)∈ F₂ⁿ such that aᵢ=Tr₂ₙ|₂(α¹⁺²ⁱ) for 0≤ i≤ n-1, where n is a 2-power or odd, if and only if the given vector a is symmetric (aᵢ=aₙ₋ᵢ for all i, 1≤ i≤ n-1), and one of the following is true. 1) n=2ˢ≥ 4, a₀=1, aₙ/₂=0, ∑₁≤ ᵢ≤ ₙ/₂₋₁, ₍ᵢ,₂₎₌₁aᵢ=1; 2) n is odd, (∑₀≤ ᵢ≤ ₙ₋₁aᵢxⁱ,xⁿ-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 F₂ₙ over F₂ are given. And for all n with 4|n, we prove that there exists a normal element of F₂ₙ over F₂ such that the Hamming weight of its corresponding vector is 3, which is the lowest possible Hamming weight.