Aufgaben:Exercise 2.1: Group, Ring, Field

• Return to book

„Addition” und „Multiplikation” für  $q = 3$  und  $q = 4$

Im  Theorieteil  zu diesem Kapitel wurden verschiedene algebraische Begriffe definiert. Für das Folgende setzen wir voraus, dass alle Mengen aus jeweils  $q$  Elementen bestehen, wobei hier entweder  $q = 3$  oder  $q = 4$  gelten soll. Dann gilt:

• Eine  algebraische Gruppe  ist eine endliche Menge  $G = \{0, \, 1, \hspace{0.05cm}\text{...} \hspace{0.1cm} , \ q-1\}$  zusammen mit einer zwischen allen Elementen definierten Verknüpfungsvorschrift. Eine additive Gruppe wird mit  $(G, \ +)$  bezeichnet, eine multiplikative mit  $(G, \ \cdot)$.

• Ein  algebraischer Ring  kennzeichnet eine Menge  $R = \{0, \, 1, \hspace{0.05cm}\text{...} \hspace{0.1cm} , \ q-1\}$  zusammen mit zwei darin definierten Rechenoperationen, nämlich der Addition  („$+$”)  und der Multiplikation  („$\hspace{0.05cm}\cdot\hspace{0.05cm}$”).

• Ein  algebraischer Körper  ist ein Ring, bei dem zusätzlich die Division erlaubt ist und das Kommutativgesetz erfüllt wird.

Da wir hier ausschließlich endliche Mengen betrachten, ist ein Körper (englisch:  Field) gleichzeitig ein Galoisfeld  ${\rm GF}(q)$  der Ordnung  $q$.

Eine wesentliche Eigenschaft des Galoisfeldes  ${\rm GF}(q) = \{\hspace{0.1cm}z_0,\hspace{0.1cm} z_1,\hspace{0.05cm}\text{...} \hspace{0.1cm} , \hspace{0.1cm}z_{q-1}\}$  ist, dass es mindestens ein primitives Element besitzt. Ein Element  $z_i ≠ 0$  bezeichnet man als primitiv, wenn die folgende Bedingung erfüllt ist  $(k$ ist ganzzahlig$)$:

$$z_i^k \hspace{0.15cm}{\rm mod}\hspace{0.15cm}q = \left\{ \begin{array}{c} \ne 1\\ 1 \end{array} \right.\quad \begin{array}{*{1}c} {\rm f\ddot{u}r} \hspace{0.15cm}1 \le k < q-1 \\ {\rm f\ddot{u}r} \hspace{0.15cm}k = q-1 \\ \end{array} \hspace{0.35cm} \Rightarrow \hspace{0.35cm} z_i \hspace{0.15cm}{\rm ist \hspace{0.15cm}ein\hspace{0.15cm} primitives \hspace{0.15cm}Element} \hspace{0.05cm}. $$

Nur bei einem primitiven Element  $z_i$  ergeben sich durch die Rechenoparation  $z_i^k$  $($mit  $k = 1, \, 2, \, 3, \, \hspace{0.05cm}\text{...} )$ alle Elemente des Galoisfeldes mit Ausnahme des Nullelementes $z_0 = 0$.

Hinweise:

• Die Aufgabe behandelt das Themengebiet des Kapitels  Einige Grundlagen der Algebra.
• Beachten Sie, dass bei Gruppe, Ring und Körper mit jeweils  $q$  Elementen die Rechenoperationen „$+$” und „$\hspace{0.05cm}\cdot\hspace{0.05cm}$” jeweils modulo  $q$  zu verstehen sind.

Fragebogen

1

Welche der angegebenen Tabellen beschreiben eine Gruppe?

	Tabelle  $\rm A3$,
	Tabelle  $\rm M3$,
	Tabelle  $\rm A3$  und Tabelle  $\rm M3$  gemeinsam,
	Tabelle  $\rm A4$  und Tabelle  $\rm M4$  gemeinsam.

2

Welche der angegebenen Tabellen beschreiben einen Ring?

	Tabelle  $\rm A3$,
	Tabelle  $\rm M3$,
	Tabelle  $\rm A3$  und Tabelle  $\rm M3$  gemeinsam,
	Tabelle  $\rm A4$  und Tabelle  $\rm M4$  gemeinsam,
	Tabelle  $\rm A3$  und Tabelle  $\rm M4$  gemeinsam.

3

Welche der Tabellen beschreiben einen Körper bzw. ein Galoisfeld?

	Tabelle  $\rm A3$,
	Tabelle  $\rm M3$,
	Tabelle  $\rm A3$  und Tabelle  $\rm M3$  gemeinsam,
	Tabelle  $\rm A4$  und Tabelle  $\rm M4$  gemeinsam.

4

Welche Elemente der Menge  $\{0, \, 1, \, 2\} \ \Rightarrow \ q = 3$  sind primitiv?

	$z_0 = 0$,
	$z_1 = 1$,
	$z_2 = 2.$

5

Welche Elemente der Menge  $\{0, \, 1, \, 2, \, 3\} \ \Rightarrow \ q = 4$  sind primitiv?

	$z_0 = 0$,
	$z_1 = 1$,
	$z_2 = 2$,
	$z_3 = 3$.

Musterlösung

Solution

(1)  Mit der Zahlenmenge $Z_3 = \{0, \, 1, \, 2\}$ beschreibt

• die Tabelle A3 die additive Gruppe $(Z_3, \, +)$,
• die Tabelle M3 die multiplikative Gruppe $(Z_3, \, \cdot)$.

⇒   Lösungsvorschlag 1 und 2. Die Lösungsvorschläge 3 und 4 treffen dagegen hier nicht zu, da bei einer Gruppe jeweils nur eine Rechenoperation (Addition oder Multiplikation) definiert ist.

(2)  Auf einem algebraischen Ring sind im Gegensatz dazu zwei Rechenoperationen definiert. Richtig sind somit die Lösungsvorschläge 3 und 4:

• Die Tabellen A3 und M3 beschreiben den Ring $(Z_3, \, +, \, \cdot)$.
• Die Tabellen A4 und M4 beschreiben den Ring $(Z_4, \, +, \, \cdot)$.

Dagegen beschreiben A3 und M4 keinen Ring, da sie sich auf unterschiedliche Mengen beziehen.

(3)  Jeder Körper ist gleichzeitig auch ein Ring, aber nicht jeder Ring ist auch ein Körper:

• Bei letzterem ist auch die Division definiert und es gibt für jedes Element auch die multiplikative Inverse.
• Ein endlicher Zahlenring der Ordnung $q$ (also mit $q$ Elementen) ist nur dann ein Körper, wenn $q$ eine Primzahl ist.
• Man spricht dann auch von einem Galoisfeld ${\rm GF}(q)$.

Richtig ist also die Antwort 3:

• Die Rechenoperationen gemäß den Tabellen A3 und M3 ergeben zusammen das Galoisfeld ${\rm GF}(3)$.
• Dagegen führen die Tabellen A4 (Addition) und M4 Multiplikation) zusammen mit der Menge $\{0, \, 1, \, 2, \, 3\}$ nicht zum Galoisfeld ${\rm GF}(4)$.
• Eine Bedingung für ein Galoisfeld ist, dass es für jedes Element $z_i$ eine multiplikative Inverse ${\rm Inv}_{\rm M}{(z_i)}$ gibt, so dass die Gleichung $z_i \cdot {\rm Inv}_{\rm M}(z_i) = 1$ erfüllt ist.
• Nach Tabelle M4 existiert $\rm Inv_M(2)$ aber nicht. In der dritten Zeile gibt es keine „$1$”.

Ein Galoisfeld $\rm GF(4)$ ergibt sich zum Beispiel durch Erweiterung der binären Menge $\{0, \, 1\}$ zur Menge $\{0, \, 1, \, \alpha, \, 1+\alpha\}$. Genaueres hierzu finden Sie auf der Seite Beispiel eines Erweiterungskörpers.

(4)  Das Nullelement ist nie ein primitives Element. Auch $z_1 = 1$ ist kein primitives Element, denn dann müsste mit $q = 3$ gelten:

$$z_1^1 \hspace{0.15cm}{\rm mod\hspace{0.15cm}} 3\hspace{0.1cm} \ne 1 \hspace{0.05cm},\hspace{0.3cm}z_1^2 \hspace{0.15cm}{\rm mod\hspace{0.15cm}} 3\hspace{0.1cm} = 1 \hspace{0.05cm}.$$

Dagegen ist $z_2 = 2$ ein primitives Element wegen

$$2^1 \hspace{0.15cm}{\rm mod\hspace{0.15cm}} 3\hspace{0.1cm} = 2 \hspace{0.05cm},\hspace{0.3cm}2^2 \hspace{0.15cm}{\rm mod\hspace{0.15cm}} 3\hspace{0.1cm} = 1 \hspace{0.05cm}.$$

Richtig ist also der Lösungsvorschlag 3.

(5)  Die Menge $\{0, \, 1, \, 2, \, 3\}$ besitzt kein primitives Element und erfüllt dementsprechend auch nicht die Erfordernisse eines Galoisfeldes:

$$z_1 \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 1\text{:}\hspace{0.35cm} 1^1 = 1\hspace{0.05cm},\hspace{0.1cm}1^2 = 1\hspace{0.05cm},\hspace{0.1cm}1^3 = 1\hspace{0.05cm},$$

$$z_2 \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 2\text{:}\hspace{0.35cm} 2^1 = 2\hspace{0.05cm},\hspace{0.1cm}2^2 \hspace{0.15cm}{\rm mod}\hspace{0.15cm}4 = 0 \hspace{0.05cm},\hspace{0.1cm}2^3 \hspace{0.15cm}{\rm mod}\hspace{0.15cm}4 = 0\hspace{0.05cm},$$

$$z_3 \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 3\text{:}\hspace{0.35cm} 3^1 = 3\hspace{0.05cm},\hspace{0.1cm}3^2 \hspace{0.15cm}{\rm mod}\hspace{0.15cm}4 = 1 \hspace{0.05cm},\hspace{0.1cm}3^3 \hspace{0.15cm}{\rm mod}\hspace{0.15cm}4 = 3\hspace{0.05cm}.$$