Aufgaben:Exercise 2.4Z: Finite and Infinite Fields

• Return to book

Some pioneers of mathematics

In mathematics,  different sets of numbers are distinguished:

• the set of natural numbers:  $\mathcal{N} = \{0, \, 1, \, 2, \hspace{0.05cm}\text{ ...} \}$,

• the set of integers:  $\mathcal{Z} = \{\text{ ...}, \, -1, \, 0, \, +1, \hspace{0.05cm}\text{ ...} \}$,

• the set of rational numbers:  $\mathcal{Q} = \{m/n\}$   with   $m ∈ \mathcal{Z}, \ n ∈ \mathcal{Z} \, \backslash \, \{0\}$,

• the set  $\mathcal{R}$  of real numbers,

• the set of complex numbers:  $\mathcal{C}= \{a + {\rm j} \cdot b\}$  with   $a ∈ \mathcal{R}, \ b ∈ \mathcal{R}$  and the imaginary unit  "$\rm j$".

Such a set is called a  "field"  in the algebraic sense if  (and only if)  the four arithmetic operations addition, subtraction, multiplication and division are allowed in it and the results are representable in the same field.

Some related definitions can be found in the  "theory section".  So much up front:  Not all of the sets listed here are fields.

Besides,  there are also  "finite fields",  which in our learning tutorial are also called  "Galois field"  ${\rm GF}(P^m)$  where

• $P ∈ \mathcal{P}$  denotes a prime number, and

• $m ∈ \mathcal{N}$  denotes a natural number.

If the exponent  $m \ge 2$,  it is called an  "extension field".  In this exercise we restrict ourselves to extension fields to the base  $P = 2$.

The first two subtasks are related to the classification of polynomials.

• A degree-m polynomial is called  "reducible"  in the field  $\mathcal{F}$  if it is representable in the form

$$p(x)= \prod_{i = 1}^m (x-x_i) = (x - x_1) \cdot (x - x_2) \cdot \hspace{0.05cm}\text{ ...}\hspace{0.05cm} \cdot (x - x_m) $$

and holds for all zeros  $x_i ∈ \mathcal{F}$.

• If this is not possible,  one speaks of an  "irreducible polynomial".

Hints:

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

• Above you can see illustrations of the Italian mathematicians  Gerolamo Cardano  and  Rafael Bombelli, who first introduced imaginary numbers to solve algebraic equations, and of  Évariste Galois, who established the foundations of finite fields at a very young age.

Questions

1

Which polynomials are irreducible in the real field  $\mathcal{R}$?

	$p_1(x) = x^2 + 1$.
	$p_2(x) = x^2 - 1$,
	$p_3(x) = x^2 + x + 1$,
	$p_4(x) = x^2 + x - 2$.

2

Which polynomials are irreducible in  $\rm GF(2)$?

	$p_1(x) = x^2 + 1$,
	$p_2(x) = x^2 - 1$,
	$p_3(x) = x^2 + x + 1$,
	$p_4(x) = x^2 + x - 2$.

3

Which sets are fields in the algebraic sense?

	the set  $\mathcal{N}$  of natural numbers,
	the set  $\mathcal{Z}$  of integers,
	the set  $\mathcal{Q}$  of rational numbers,
	the set  $\mathcal{R}$  of real numbers,
	the set  $\mathcal{C}$  of complex numbers.

4

Which fields are subset (subspace) of another field?

	$\mathcal{Q} ⊂ \mathcal{C}$,
	$\mathcal{C} ⊂ \mathcal{R}$,
	${\rm GF}(2) ⊂ {\rm GF}(2^2)$,
	${\rm GF}(2^3) ⊂ {\rm GF}(2^2)$.

5

Which fields have certain analogies?

	Set  $\mathcal{Q}$  of rational numbers and  ${\rm GF}(2^2)$,
	set  $\mathcal{C}$  of complex numbers and  ${\rm GF}(2^2)$,
	set  $\mathcal{C}$  of complex numbers and  ${\rm GF}(2^3)$.

Solution

Solution

(1)  In the data section it says accordingly:

A polynomial of degree  $m$  is called  "reducible"  in the field  $\mathcal{F}$  if it is can be represented the form

$$p(x)= \prod_{i = 1}^m (x-x_i) = (x - x_1) \cdot (x - x_2) \cdot \hspace{0.05cm}\text{ ...}\hspace{0.05cm} \cdot (x - x_m) $$

and this is valid for all zeros  $x_i ∈ \mathcal{F}$.   If this is not possible,  one speaks of an  "irreducible"  polynomial.

In real number space,  it hold for the  $m = 2$  zeros  $x_1$  and  $x_2$:

$$p_1(x) \text{:}\hspace{0.3cm}x_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} +{\rm j}\hspace{0.05cm},\hspace{0.2cm}x_2 = -{\rm j}\hspace{0.05cm},$$

$$p_2(x) \text{:}\hspace{0.3cm}x_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} +1\hspace{0.05cm},\hspace{0.2cm}x_2 = -1\hspace{0.05cm},$$

$$p_3(x) \text{:}\hspace{0.3cm}x_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} -0.5 + {\rm j} \cdot \sqrt{3}/2 \hspace{0.05cm},\hspace{0.2cm}x_2 = -0.5 - {\rm j} \cdot \sqrt{3}/2\hspace{0.05cm},$$

$$p_4(x) \text{:}\hspace{0.3cm}x_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} +1\hspace{0.05cm},\hspace{0.2cm}x_2 = -2\hspace{0.05cm}.$$

Thus the  proposed solutions 1 and 3  are correct:

• The two zeros of  $p_2(x)$  and  $p_4(x)$  are both real.  Thus,  these are certainly reducible polynomials.

• The other two polynomials,  on the other hand,  have no real zeros  (rather imaginary or complex ones)  and they are irreducible in the real field according to the above definition.

(2)  Correct is the  proposed solution 3:

$p_3 = x^2 + x + 1$  is the only irreducible polynomial in the Galois field  $\rm GF(2^2)$.  In the "theory section"  the additions and the multiplication table were given for this.

For the other polynomials holds:

• The polynomial  $p_1(x)$  is reducible in  ${\rm GF}(2) = \{0, \, 1\}$  since this polynomial can be factorized:

$$p_1(x) = x^2 + 1 = (x+1)^2\hspace{0.05cm}.$$

• Since in  $\rm GF(2)$  there is no difference between sum and difference,  the polynomial  $p_2(x) = x^2 - 1$  is also reducible.

• The polynomial  $p_4(x) = x^2 + x - 2$  is  unsuitable for  $\rm GF(2)$  alone,  since not all polynomial coefficients are  $0$  or  $1$.  The  "$2$"  would only be possible in the Galois field  $\rm GF(3)$.

(3)  Correct are the  last three proposed solutions:

• The set  $\mathcal{N}$  is not a field,  since already the subtraction is not allowed for all elements,  for example  $2 - 3 = -1 ∉ \mathcal{N}$.

• Also the set  $\mathcal{Z}$  of integers is not a field,  since for example the equation  $2 \cdot z = 1$  is not to be satisfied for any  $z ∈ \mathcal{N}$.

(4)  Correct are  the answers 1 and 3:

• It is  $\mathcal{Q} ⊂ \mathcal{R}$  (rational numbers are a subset of real numbers)  and  $\mathcal{R} ⊂ \mathcal{C}$  (real numbers are a subset of the complex numbers).

• Thus also  $\mathcal{Q} ⊂ \mathcal{C}$.
• For finite fields,  ${\rm GF}(2^m) ⊂ {\rm GF}(2^M)$  means that  $m < M$  must hold.

(5)  Correct is only the  proposed solution 2:

• The set  $\mathcal{C}$  of complex numbers is an extension of the real numbers  $(\mathcal{R})$  into a second dimension.  For this can be written:

$$\mathcal{C} = \{k_0 + {\rm j} \cdot k_1\hspace{0.05cm}| \hspace{0.05cm}k_0 \in {\mathcal{R}}, k_1 \in \mathcal{R}\}\hspace{0.05cm}.$$

• $\rm GF(2^2)$  is an extension of the finite field  $\rm GF(2) = \{0, \, 1\}$  into a second dimension:

$${\rm GF}(2^2) = \{k_0 + \alpha \cdot k_1\hspace{0.05cm}| \hspace{0.05cm}k_0 \in {\rm GF}(2), k_1 \in {\rm GF}(2)\}\hspace{0.05cm}.$$

• The imaginary unit  ${\rm j} ∉ \mathcal{C}$  results as the solution of the equation   ${\rm j}^2 + 1 = 0$,  while the new element of  $\rm GF(2^2)$  is denoted by  $\alpha ∉ \rm GF(2)$  and follows from the equation   $\alpha^2 + \alpha + 1 = 0$.