I am interested in constructing type $k$ Gaussian normal basis (GNB) for $GF(2^n)$. I found a construction theorem in The Gaussian normal basis and its trace basis over finite fields which states the following theorem.
The construction theorem for a type $k$ Gaussian normal basis for $GF(q^n)$.
Let $q$ be a power of the prime $p$, $k$ and $n$ be positive integers such that $kn + 1$ is a prime and $gcd(kn + 1, p) = 1$. Assume that $γ ∈ F_{q^{kn}}$ is a primitive $(kn + 1)$-th root of unity and $s$ is the order of $q$ (mod $kn + 1$). If $gcd(kn/s,n) = 1$, then for any primitive $k$-th root $ι ∈ Z^*_{kn+1}$ of unity,
$$ α = \sum_{i=0}^{k-1} γ^{ι^i} $$ generates a normal basis $N$ of $F_{q^n}$ over $F_q$.
To understand this theorem, I try deriving some examples according to Cetin Kaya Koc's slide on Normal and Optimal Normal Bases.
First, I try to construct type $1$ GNB for $GF(2^4)$ using irreducible polynomial $x^4+x+1$, I have
- $p=2, q=2^1,k=1,n=4$
- $kn+1=5$ is prime, and $gcd(5,2)=1$
- $γ ∈ F_{q^{kn}}$ $(F_{2^4})$ is a primitive $5$-th root of unity ($γ^5=1$ (mod $x^4+x+1$)), which are $x^3, x^3+x, x^3+x^2$ and $x^3+x^2+x$
- $s =$ order of $2$ in $Z^*_{kn+1}$ $(Z^*_{5})=4$, and $gcd(kn/s,n)=1$
- $ι ∈ Z^*_{kn+1}$ $(Z^*_5)$ is any primitive $1$-st root of unity, which is 1.
- Hence, $α = \sum_{i=0}^{k-1} γ^{ι^i} = γ$, and any $γ$ can be used as GNB.
However, when I try to construct type $2$ GNB for $GF(2^5)$ using irreducible polynomial $x^5+x^2+1$, I have
- $p=2, q=2^1,k=2,n=5$
- $kn+1=11$ is prime, and $gcd(11,2)=1$
- $γ ∈ F_{q^{kn}}$ $(F_{2^{10}})$ is a primitive $11$-th root of unity.
Here, I'm not sure how to find $γ$, since no irreducible polynomial in $F_{2^{10}}$ is given.
I'm not sure if there is something wrong, or I misunderstand some points of the theorem.
Any help would be appreciated. Thanks.
The idea here is actually to look for a basis $S$ of the field $GF(2^n)$ over $GF(2)$ such that for any pair of elements $x,y\in S$ their product can be written as a linear combination of as few basis elements as possible in the average. When you implement the arithmetic of the field on a computer, multiplication then becomes faster. Observe that as soon as we know the product rule of the basis elements, we have fully described the field. Unless we really want to, there is no compelling need to tie this together with the construction of $GF(2^n)$ as the quotient ring $GF(2)[x]/\langle p(x)\rangle$ for some irreducible polynomial $p(x)$ of degree $n$.
Working out the process of finding a normal basis of the field $GF(2^5)$ that you started with, and explaining bits and pieces while I go.
So $p=2,q=2^1$, $n=5$. Because $1\cdot n+1=6$ is even, we cannot use $k=1$. The choice $k=2$ is more promising. Particularly as $2\cdot5+1=11$ has the nice property that $2$ is a generator for the multiplicative group $\Bbb{Z}_{11}$. In other words the order of $2$ modulo $11$ is equal to $s=10$. We observe that $$ \iota=2^5\equiv10\pmod{11} $$ is a primitive root of order two. As $10\equiv-1$ this is kinda obvious, but when we are forced to use a larger $k$, this may become a bit messier.
So next we let $\gamma$ be a primitive eleventh root of unity. The theory tells us, as you observed, that such an element exists in the field $GF(2^{10})$. The beauty here is that we actually don't need to know anything else about $\gamma$. These facts are all we need!
Next we construct the element $$ \alpha=\gamma+\gamma^\iota=\gamma+\gamma^{-1}. $$ The theory says that $\alpha$ is an element of $GF(32)$. How can we be sure of that? Recall that the elements $z$ of $GF(32)$ are characterized by the fact that they satisfy the equation $z^{32}=z$. Let's check. By Freshman's dream $$ \alpha^{32}=\gamma^{32}+\gamma^{-32}. $$ Here $32\equiv-1\pmod{11}$ (it always happens that $q^n\equiv\iota \pmod{kn+1}$ that is by design). Therefore $$\gamma^{32}=\gamma^{33-1}=(\gamma^{11})^3\gamma^{-1}=\gamma^{-1}$$ and similarly $\gamma^{-32}=\gamma$. Consequently $\alpha^{32}=\alpha$ to our satisfaction.
The element $\alpha$ is to generate a normal basis, i.e. the theorem says that $S=\{\alpha,\alpha^2,\alpha^4,\alpha^8,\alpha^{16}\}$ is a basis for $GF(32)$ over $GF(2)$. Let's take a look at the basis elements in terms of $\gamma$. We get $$ \begin{aligned} \alpha&&=\gamma+\gamma^{-1},\\ \alpha^2&&=\gamma^2+\gamma^{-2},\\ \alpha^4&&=\gamma^4+\gamma^{-4},\\ \alpha^8&=\gamma^8+\gamma^{-8}&=\gamma^3+\gamma^{-3},&\quad\text{here $-3\equiv8\pmod{11}$ so $\gamma^{\pm8}=\gamma^{\mp3}$}\\ \alpha^{16}&=\gamma^{16}+\gamma^{-16}&=\gamma^5+\gamma^{-5},&\quad\text{as $16\equiv5\pmod{11}.$} \end{aligned} $$ Observe that all the ten non-trivial powers of $\gamma$ appear - each exactly once and together with its reciprocal. What this means is that the choice of $\gamma$ is immaterial (as I promised!). The basis $S$ gets exactly the same elements of $GF(32)$ irrespective of whether we picked, say $\gamma^7=\gamma^{-4}$ instead of the chosen $\gamma$.
Why is this cool? One of the points here is can now quite effortlessly write down the multiplication table of $S$. Behold: $$ \begin{aligned} \alpha\cdot\alpha&&&=\alpha^2&\quad\text{(d'uh)}\\ \alpha\cdot\alpha^2&=\gamma^3+\gamma^1+\gamma^{-1}+\gamma^{-3}&&=\alpha+\alpha^8,\\ \alpha\cdot\alpha^4&=\gamma^5+\gamma^3+\gamma^{-3}+\gamma^{-5}&&=\alpha^8+\alpha^{16},\\ \alpha\cdot\alpha^8&=\gamma^4+\gamma^2+\gamma^{-2}+\gamma^{-4}&&=\alpha^2+\alpha^4,\\ \alpha\cdot\alpha^{16}&=\gamma^6+\gamma^4+\gamma^{-4}+\gamma^{-6}&&=\alpha^4+\alpha^{16}&\quad(\gamma^6=\gamma^{-5}). \end{aligned} $$ We see that, on the average we get a bit less than two terms in the final forms of products. This is because we stumbled upon an optimal normal basis. Those don't exist for all the fields. The cases $k=1$ and $k=2$ are special.
Observe that the rest of the products follow the cyclic pattern determined by the action of the Galois group (read: Frobenius automorphism). For example $$ \alpha^4\cdot\alpha^8=(\alpha\cdot\alpha^2)^4=(\alpha+\alpha^8)^4= \alpha^4+\alpha^{32}=\alpha^4+\alpha. $$
You were (very naturally!) concerned about how this interacts with the construction of the field $GF(32)$ using an irreducible polynomial. With the above multiplication tables at hand we can actually figure out the minimal polynomial of $\alpha$. To that end we need to observe that as $$ 0=\frac{\gamma^{11}-1}{\gamma-1}=\gamma^{10}+\gamma^9+\cdots+\gamma+1 $$ we have the linear relation (really the minimal polynomial of $\gamma$): $$ 0=\gamma^5+\gamma^4+\cdots+\gamma+1+\gamma^{-1}+\cdots+\gamma^{-5}.\qquad(*) $$ From this we read that the neutral element of our field $GF(32)$ is $$ 1=\alpha+\alpha^2+\alpha^4+\alpha^8+\alpha^{16}. $$ This is typical of normal bases - the presentation of $1$ is kinda complicated. Anyway, I leave it to you to check either using the identity $(*)$ or the multiplication table that our element $\alpha$ satisfies the equation $$ \alpha^5+\alpha^4+\alpha^2+\alpha+1=0.\qquad(**) $$ You can read the minimal polynomial $m(x)=x^5+x^4+x^2+x+1$ from here.
So you can identify the elements of this optimal normal basis within the construction $GF(32)=GF(2)[x]/\langle x^5+x^2+1\rangle$ by looking for zeros of $m(x)$.
The picture I painted here is perhaps misleadingly tidy. Here the coincidence that $s=kn$ gave too clean a picture, because without that "accident" the minimal polynomial of $\gamma$ is more complicated to find. This is one of the reasons why optimal normal bases are particularly nice.