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 above 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 ≥ is 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 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) $$

is representable 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 fields".
• 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 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) $$

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

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

$$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 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 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 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$ .