Standard basis representation of elements in binary field

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?

• "Basis" here means a basis of $\mathbf F_{2^n}$ as a $\mathbf F_2$-vector space. May 2 '19 at 2:37

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.

• I think I understand - but want to confirm: so, we still have $2^n-1$ field elements - we just express them differently. Specifically, we use polynomial basis. For example, if $g=2$, polynomial basis $\{1, g, g^2\}$ would be $\{1, 2, 4\}$, and field elements would be expressed as $\{1, g, g+1,g^2,g^2+1,g^2+g,g^2+g+1\}$ or just $\{1,2,3,4,5,6,7\}$. Is this correct? May 2 '19 at 6:22
• No, a base must represent all of the elements. The $g$ cannot be 2 and it is not even elements of the $\mathbb{F}_8 = \mathbb{F}_{2^3} \neq Z_8$. The field extensions are formed adding a root of an irreducible polynomial to the base field. As you know, when you added $i$ into $\mathbb{R}$ you get $\mathbb{C}$. Here it is like; let $\alpha$ be the root of an irreducible polynomial of degree $m$ (also, $m$ is the extension degree), then we can form a polynomial basis to express all the elements. May 2 '19 at 8:25
• Hmmm, maybe I shouldn't have used integers to express elements in $\mathbb{F}_8$, but it seems I'm still missing something. Here is what I think I get: (1) there are 7 multiplicative elements in $\mathbb{F}_8$, and these elements are $\{1, x, x + 1, x^2, x^2+1, x^2+x, x^2+x+1\}$; (2) polynomial basis of $\mathbb{F}_8$ are $\{1, g, g^2\}$ for some $g \in \mathbb{F}_8$; (3) we can use polynomial basis to express every element in $\mathbb{F}_8$ as $\{1, g, g+1, g^2, g^2+1, g^2+g, g^2+g+1\}$. Where am I going wrong? May 2 '19 at 15:54
• You are confusing a generator of the multiplicative cyclic group of the field and base elements. Linear combination of the base elements represents all the elements of the field, including 0. Updated the answer, too. May 2 '19 at 16:44
• The field has $2^n$ elements, including zero. May 2 '19 at 23:49