Standard basis representation of elements in binary field

Question

In Remark B.1 from this paper it says:

We assume canonical representation for binary fields $\mathbb{F}$, given by an irreducible polynomial and a primitive element $g \in \mathbb{F}$ for it (i.e., $g$ generates $\mathbb{F}^*$). We use the standard basis {${1, g, g^2, ..., g^{n-1}}$} to represent $\mathbb{F}_{2^n}$ over $\mathbb{F}_2$.

I think I understand the first sentence, but the second sentence confuses me. Shouldn't there be $2^{n}-1$ elements generated by $g$? If so, the elements would be {${1, g, g^2, ..., g^{2^n-1}}$} - right? Am I missing something?

Answer 1

Your basis is the polynomial basis.

The terminology basis comes from adopting a finite extension $F=\mathbb{F}_{q^m}$ of the finite field $K=\mathbb{F}_{q}$ as a vector space over $K$. We can see that the extension as the dimension of the vector space so we need $m$ elements to form a base.

1. Polynomial Basis

   Let $K$ be a degree $m$ extension of the finite Field $F$ and let $\alpha$ be a root of a primitive polynomial of degree $m$ then the powers of $\alpha$ (defining elements) forms a polynomial basis. $$\{1,\alpha,\alpha^2,\ldots,\alpha^{m-1} \}$$

   Example: Let $\alpha \in \mathbb{F}_8$ be a root of an irreducible polynomial in $x^3+x^2+1$ in $\mathbb{F}_2$. Then, $\{1,\alpha,\alpha^2\}$ is a polynomial base. With this base the 8 elements of the extension field can be represented as;

   $$\{0,1,\alpha, \alpha +1, \alpha^2, \alpha^2+1, \alpha^2+\alpha, \alpha^2+\alpha+1\}$$

   When we talk about the multiplicative cyclic group $F^*$ of the field $F$, the element zero is excluded $$F^*= F \backslash \{0\}.$$

   In this example;

   $$\mathbb{F}^*_8= \{1,\alpha, \alpha +1, \alpha^2, \alpha^2+1, \alpha^2+\alpha, \alpha^2+\alpha+1\}$$

   In this multiplicative cyclic group, there are elements $g$ such that $F^*=\langle g \rangle$

2. Normal Basis

   Let $K = \mathbb{F}_q$ and $F = \mathbb{F}_{q^m}$. Then a basis of $F$ over $K$ of the form $\{\alpha, \alpha^q, \ldots, \alpha^{q^{m-1}}\}$, consisting a suitable element $\alpha \in F$ and its conjugates with respect to $K$, is called a normal basis of $F$ over $K$

Note: these two are not the only basis that we can form, these two is the well-known basis.