Aufgaben:Exercise 2.5: Three Variants of GF(2 power 4)

• Return to book

Powers of two different extension fields over $\rm GF(2^4)$ - a not quite complete list

Irreducible and primitive polynomials have great importance in the description of error correction methods.  For example,  in  [LN97]  one finds the following irreducible polynomials of degree  $m = 4$:

• $p_1(x) = x^4 + x +1$,

• $p_2(x) = x^4 + x^3 + 1$,

• $p_3(x) = x^4 + x^3 + x^2 + x + 1$.

The first two polynomials are also primitive.  This can be seen from the power tables given on the right – the lower table  $\rm (B)$  however not quite complete.

• From both tables we see that all powers  $\alpha^i$  for   $1 ≤ i ≤ 14$   are unequal  $1$  in the polynomial representation.  Only for  $i = 15$  it follows that

$$\alpha^{15} = \alpha^{0} = 1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}{\rm Coefficient\hspace{0.15cm}vector\hspace{0.15cm} 0001}\hspace{0.05cm} .$$

• It is not specified whether the tables  $\rm (A)$  and  $\rm (B)$  result from the polynomial   $p_1(x) = x^4 + x + 1$   or from   $p_2(x) =x^4 + x^3 + 1$.   You are to make these assignments in subtasks  (1)  and  (2).

• In the subtask  (3)  you are also to complete the missing powers  $\alpha^5, \ \alpha^6, \ \alpha^7$  and  $\alpha^8$  in the table  $\rm (B)$.

• The subtask  (4)  refers to the also irreducible polynomial   $p_3(x) = x^4 + x^3 + x^2 + x +1$.  According to the above criteria,  you are to decide whether this polynomial is primitive.

Hints:

• The exercise belongs to the chapter  "Extension Field".

• The literature citation  [LN97]  refers to the book  "Lidl, R.; Niederreiter, H.:  Finite Fields.  Encyclopedia of Mathematics and its Application. 2nd ed. Cambridge: University Press, 1997."

Questions

1

Which polynomial underlies the table  $\rm (A)$ ?

	$p_1(x) = x^4 + x + 1$,
	$p_2(x) = x^4 + x^3 + 1$.

2

Which polynomial underlies the table  $\rm (B)$ ?

	$p_1(x) = x^4 + x + 1$,
	$p_2(x) = x^4 + x^3 + 1$.

3

Complete the entries missing in the table  $\rm (B)$.  Which of the following entries are correct?

	$\alpha^5 = \alpha^3 + \alpha + 1$   ⇒   Coefficient vector  "$1011$",
	$\alpha^6 = \alpha^2 + 1$   ⇒   Coefficient vector  "$0111$",
	$\alpha^7 = \alpha^3 + \alpha^2 + \alpha + 1$   ⇒   Coefficient vector  "$1111$"
	$\alpha^8 = \alpha^3 + \alpha^2 + \alpha$   ⇒   Coefficient vector  "$1110$".

4

Is the polynomial   $p_3(x) = x^4 + x^3 + x^2 + x + 1$   primitive?  Clarify this question using the powers  $\alpha^i$  $(i$  where necessary$)$.

	Yes.
	No.

Solution

Solution

(1)  From the upper power table  $\rm (A)$  on the data page one recognizes among other things the property

$$\alpha^{4} = \alpha + 1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}\alpha^{4} + \alpha + 1 = 0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} p(x) = x^4 + x +1 =p_1(x)\hspace{0.05cm}.$$

Thus, the proposed solution 1 is correct.

(2)  Following the same procedure, it can be shown that the power table  $\rm (B)$  is based on the polynomial $p_2(x) = x^4 + x^3 + 1$   ⇒   Proposed solution 2.

(3)  Starting from polynomial $p_2(x) = x^4 + x^3 + 1$ one obtains from the determining equation $p(\alpha) = 0$ the result $\alpha^4 = \alpha^3 + 1$. This further yields:

$$\alpha^5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^4 = \alpha \cdot (\alpha^3 + 1) = \alpha^4 + \alpha = \alpha^3 + \alpha +1\hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vector\hspace{0.15cm} 1011},$$

$$\alpha^6 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^5 = \alpha \cdot (\alpha^3 +\alpha + 1) = \alpha^4 + \alpha^2 + \alpha= \alpha^3 +\alpha^2 + \alpha + 1\hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vector\hspace{0.15cm} 1111},$$

$$\alpha^7 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^6 = \alpha^4 +\alpha^3 +\alpha^2 +\alpha = \alpha^2 + \alpha + 1\hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vector\hspace{0.15cm} 0111},$$

$$\alpha^8 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^7 = \alpha \cdot (\alpha^2 + \alpha + 1) = \alpha^3 +\alpha^2 +\alpha \hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vector\hspace{0.15cm} 1110}.$$

• Thus, only the proposed solutions 1 and 4 are correct. The other two statements are interchanged.
• The following are the complete power tables for $p_1(x) = x^4 + x + 1$ (left, red background) and for $p_2(x) = x^4 + x^3 + 1$ (right, blue background).

Complete power tables over $\rm GF(2^4)$ for two different polynomials

(4)  The two polynomials  $p_1(x) = x^4 + x + 1$  and  $p_2(x) = x^4 + x^3 + 1$  are primitive.

• This can be seen from the fact that $\alpha^i$ is not equal to $1$ for $0 < i < 14$ in each case.
• In contrast, $\alpha^{15} = \alpha^0 = 1$ holds. In both cases, the Galois field can be expressed as follows:

$${\rm GF}(2^4) = \{\hspace{0.1cm}0\hspace{0.05cm},\hspace{0.1cm} \alpha^{0} = 1,\hspace{0.05cm}\hspace{0.1cm} \alpha\hspace{0.05cm},\hspace{0.1cm} \alpha^{2},\hspace{0.1cm} ... \hspace{0.1cm} , \hspace{0.1cm}\alpha^{14}\hspace{0.1cm}\}\hspace{0.05cm}. $$

For the polynomial  $p_3(x) = x^4 + x^3 + x^2 + x +1$  we get:

$$\alpha^4 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha^3 + \alpha^2 + \alpha +1\hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm Vector\hspace{0.15cm} 1111}\hspace{0.05cm},$$

$$\alpha^5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^4 = \alpha^4 + \alpha^3 + \alpha^2 + \alpha = (\alpha^3 + \alpha^2 + \alpha +1) + \alpha^3 + \alpha^2 + \alpha = 1 \hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm Vector\hspace{0.15cm} 0001}\hspace{0.05cm}.$$

• So here already $\alpha^5 = \alpha^0 = 1 \Rightarrow \ p_3(x)$ is not a primitive polynomial   ⇒   Proposed solution 2.
• For the other powers, this polynomial holds:

$$\alpha^6 = \alpha^{11} = \alpha\hspace{0.05cm},\hspace{0.2cm} \alpha^7 = \alpha^{12} = \alpha^2\hspace{0.05cm},\hspace{0.2cm} \alpha^8 = \alpha^{13} = \alpha^3\hspace{0.05cm},$$

$$\alpha^9 = \alpha^{14} = \alpha^4\hspace{0.05cm},\hspace{0.2cm} \alpha^{10} = \alpha^{15} = \alpha^0 = 1\hspace{0.05cm}.$$