2 Endliche Strukturen

2.1 Multiplikative ABEL’sche Gruppen

Entsprechend Abschnitt 1.1.2 handelt es sich bei endlichen kommutativ-multiplikativen Gruppen um algebraische Strukturen 𝐺^∗ := (𝐺,·), welche bzgl. der Multiplikation

• assoziativ;
• mit einem neutralen Element 𝑒_(·) = 1 ausgestattet;
• eindeutig invertierbar;
• und kommutativ

sind.⁹

2.1.1 Ordnung von Elementen

Endliche multiplikative Gruppen sind insbesondere wegen ihrer Eigenschaften beim Potenzieren von Gruppenelementen sehr interessant. Betrachten wir dazu die Folge der Potenzen 𝑟¹,𝑟²,𝑟³,𝑟⁴,… irgendeines Elements 𝑟 ∈ 𝐺^∗. Nach dem Prinzip der Abgeschlossenheit (Gruppenaxiom) wird auch jede Potenz von 𝑟 wieder in 𝐺^∗ liegen. Wegen der endlichen Zahl |𝐺^∗| von Elementen, muß sich ab irgendeiner Potenz 𝑙 ≤ |𝐺^∗| die Folge wiederholen. Eine solche Wiederholung läßt den Ansatz 𝑟^𝑖 = 𝑟^𝑙 zu. Multiplikation mit dem inversen Element von 𝑟^𝑖 ergibt 1 = 𝑟^𝑙−𝑖, was wegen 𝑙 > 𝑖 wiederum bedeutet, das es immer ein Element mit

gibt. Die Folge {𝑟,𝑟²,𝑟³,…,𝑟^𝑘−1,𝑟^𝑘 = 1 = 𝑟⁰} nennt man die vom Element 𝑟 erzeugte zyklische Untergruppe und kennzeichnet sie mit

Unter Zuhilfenahme von 𝑟^𝑘 = 𝑟⁰ läßt sich die Menge der Elemente auch so definieren:

Abbildung 1 stellt die Periodizität der Folge am Beispiel 𝑘 = 12 als Kreisteilung dar.

Die Ordnung (Anzahl der Elemente) der Untergruppe ist = 𝑘. Sie ist gleichzeitig die kleinste Potenz 𝑘, die zu 𝑟^𝑘 = 1 führt. Man nennt sie auch Ordnung des Elements 𝑟 und schreibt statt ord(𝑟) = #𝑟 = || einfach nur |𝑟|. Die Ordnung des neutralen Elements 𝑒_(·) ist 1, denn der kleinste Exponent 𝑘 der zu 𝑒_(·)^𝑘 = 𝑒_(·) führt, ist 1.¹⁰

Formel 2 gibt uns, wenn man sie mit 𝑟⁻¹ multipliziert, eine Berechnungsvorschrift für das inverse Element an die Hand:

2.1.2 Potenzen eines Elements

Betrachten wir jetzt die 𝑛-te Potenz irgendeines Elements 𝑟 und stellen die Frage nach der Ordnung des so erzeugten Elements 𝑠 = 𝑟^𝑛.

Bezeichnet man dazu mit 𝑘 = |𝑟| und 𝑙 = |𝑠| die jeweilige Ordnung, so gilt nach Beziehung 2:

und für weitere Potenzen von 𝑟^𝑘:

Unter diesen Voraussetzungen kann man

formulieren und so 𝑛𝑙 = 𝑘𝑖 schlußfolgern (Exponentenvergleich). Da sich unser Interesse auf den kleinsten Exponenten 𝑙 beschränkt, haben wir es hierbei mit der Frage nach dem kleinsten gemeinsamen Vielfachen von 𝑛 und 𝑘 zu tun. Ein Beispiel für 𝑘 = 6 und 𝑛 = 4, also lcm(𝑘,𝑛) = 12 = 4 · 3 = 6 · 2 zeigt Abbildung 2.

Obwohl mit 𝑛𝑘 = lcm(𝑛,𝑘)gcd(𝑛,𝑘) auch eine Berechnungsvorschrift zur Verfügung steht, wollen wir aus Verständnis-gründen den ausführlichen Weg beschreiten. Dazu wird unter Zuhilfenahme der Abkürzung 𝑑 = gcd(𝑘,𝑛) und mittels der Produktdarstellungen 𝑘 = 𝑘𝑑 und 𝑛 = 𝑛𝑑 zuerst der gemeinsame Teiler 𝑑 eliminiert.

(7)

Wegen der Teilerfremdheit von 𝑛 und 𝑘 kann nur die Multiplikation mit der jeweils anderen Größe zum kleinsten gemeinsamen Vielfachen lcm(𝑛,𝑘) = 𝑛𝑙 = 𝑘𝑖 führen.

Die Konsequenzen aus dem Ergebnis

sind recht interessant:

1. Die Ordnung eines durch Potenzieren erzeugten Elements 𝑠 = 𝑟^𝑛 ist immer kleiner/gleich der Ordnung des Ausgangselements 𝑟. Für den Fall gcd(|𝑟|,𝑛) = 1 ist sie maximal (siehe auch Punkt 4).

2. Als Bestätigung für den Satz von LAGRANGE (vgl. auch Abschnitt 1.1.1) ist festzustellen, daß die Ordnung von 𝑠 = 𝑟^𝑛 genau die Ordnung von 𝑟 teilt.¹¹ Im Sinne der Definition des Index einer Gruppe über deren Untergruppe, hier von über , gilt deshalb:

   

   Die Ordnung |𝑠| ist dabei (entsprechend der Bedeutung eines größten gemeinsamen Teilers) der bezüglich 𝑛 teilerfremde Anteil in |𝑟|.

3. Bei Kenntnis der Ordnung 𝑘 = |𝑟| ist automatisch die Ordnung jedes Elements in der zyklischen Untergruppe bekannt (vgl. Formel 9 mit Mengendefinition 3).
4. Zwei Elemente 𝑟 ≠ 𝑠 mit derselben Ordnung sind nach Formel 9 dadurch gekennzeichnet, daß gcd(𝑘,𝑛) = 1 gilt. Die Anzahl der zur Ordnung 𝑘 teilerfremden Zahlen (die kleiner als 𝑘 sind) entspricht damit der Anzahl von möglichen Potenzen 𝑛, für die 𝑘 = = |𝑠| wird. Aus diesem Grund wird in einer multiplikativen Gruppe die Anzahl der Elemente mit jeweils gleicher Ordnung 𝑘 genau durch EULER’s Totient-Funktion¹² 𝜙(𝑘) bestimmt.
5. Bei Kombination der Formeln 9 und 5 stellt man fest, daß sich die Ordnung eines Elements 𝑟 beim Übergang zu dessen Inversen 𝑟⁻¹ nicht ändert: |𝑟⁻¹| = |𝑟^𝑘−1| = 𝑘/gcd(𝑘,𝑘 −1) = 𝑘.

2.1.3 Beziehung zur Gruppenordnung

Variante 1 Die Ordnung der von 𝑟 erzeugten zyklischen Untergruppe ist nach dem Satz von LAGRANGE (siehe Abschnitt 1.1.1) ein Teiler der Gruppenordnung |𝐺^∗|. Man kann die Ordnung der multiplikativen Gruppe deshalb auch folgendermaßen ausdrücken [4, 1.2, Satz 3]:

(10)

Daß die Ordnung von ein Teiler von |𝐺^∗| ist, führt in Verbindung mit Gleichung 2 zu:

Anschaulich (siehe auch Abbildung 2) bedeutet dies, daß sich die Potenzen 𝑟^𝑛 nach 𝑘 Elementen periodisch wiederholen .

Variante 2 Möchte man einen Rückgriff auf den Satz von LAGRANGE vermeiden, so kann für Beziehung 10 auch der folgende Beweis angeführt werden. Multipliziere jedes der |𝐺^∗| Elemente aus 𝐺^∗ = {𝑟₁,𝑟₂,𝑟₃,…,𝑟_|𝐺^∗| } mit dem Element 𝑟, welches ebenfalls 𝐺^∗ entstammt (𝑟 ist eines der 𝑟_𝑛, mit 𝑛 = 1,2,…,|𝐺^∗|). Nach dem Prinzip der Abgeschlossenheit muß auch jedes Produkt 𝑟𝑟_𝑛 wieder in 𝐺^∗ liegen. Außerdem müssen die Produkte paarweise verschieden sein, sonst würde die Multiplikation mit dem inversen Element 𝑟⁻¹ zu zwei gleichen Elementen führen (Bed. 𝑟𝑟_𝜈 ≠ 𝑟𝑟_𝜇). Abgesehen von der Reihenfolge kann deshalb folgende eindeutige Mengenabbildung (Bijektion) angegeben werden: {𝑟𝑟₁,𝑟𝑟₂,𝑟𝑟₃,…,𝑟𝑟_|𝐺^∗| }{𝑟₁,𝑟₂,𝑟₃,…,𝑟_|𝐺^∗| }. Bildet man jetzt das Produkt aller so erzeugten Elemente

und multipliziert noch mit den Inversen 𝑟_𝑛⁻¹, dann bestätigt sich 𝑟^|𝐺∗| = 1. Einzig mögliche Schlußfolgerung aus 𝑟^|𝐺∗| = 1 und 𝑟^𝑘 = 1 kann aber (konform zu Beziehung 10) nur die sein, daß die Elementeordnung 𝑘 genau die Gruppenordnung |𝐺^∗| teilt.

2.1.4 Generatorelemente

Allgemein nennt man jede, von mindestens einem Element 𝑔 durch Potenzierung erzeugte multiplikative Gruppe, eine zyklische Gruppe (siehe Abschnitt 2.1.1). Umfaßt die von 𝑔 erzeugte Untergruppe alle Elemente der multiplikativen Gruppe 𝐺^∗ (in irgendeiner Abfolge), dann bezeichnet man 𝑔 als Generatorelement oder primitives Element.

(12)

Die Ordnung eines solchen Elements muß in diesem Sinne der Gruppenordnung entsprechen.¹³

Wie alle anderen Elemente muß auch ein Generatorelement Gleichung 2 erfüllen - aber eben nur für Generatorelemente ist |𝐺^∗| der kleinste Exponent, welcher zu 𝑔^|𝐺∗| = 1 führt. Bei Kenntnis eines Generatorelements aus 𝐺^∗ sind so nicht nur alle Elemente der multiplikativen Gruppe bekannt, sondern nach Formel 9 auch deren Ordnung.

Um die Frage zu beantworten, ob es immer mindestens ein Generatorelement gibt, rekapitulieren wir folgende Fakten:

1. Die Ordnung 𝑘 = |𝑟| eines jeden Elements teilt die Gruppenordnung (Formel 10): |𝐺^∗| = 𝑖𝑘.
2. Jedes Element 𝑟 kann durch Potenzieren aus 𝑔 erzeugt werden: 𝑟 = 𝑔^𝑛.
3. Die Ordnung |𝑔| eines Generatorelements erfüllt (wie die eines jeden anderen Elements) Formel 9: |𝑔| = |𝑔^𝑛| gcd(|𝑔|,𝑛).
4. Die Ordnung eines Generatorelements muß der Gruppenordnung entsprechen: |𝑔| = |𝐺^∗|.

Kombination der formelmäßigen Voraussetzungen ergibt:

und diese Bedingung muß für irgendeine Potenz 𝑛 = 1,2,…,|𝐺^∗| zu gewährleisten sein (und zwar eindeutig für jedes Element 𝑟). Äquivalenz 13 kann aber nur erfüllt werden, wenn man 𝑛 = 𝑖𝑛, mit gcd(𝑘,𝑛) = 1 annimmt. Die Anzahl der teilerfremden Zahlen 𝑛 kleiner als 𝑘 liefert mit 𝜙(𝑘) EULER’s Totient-Funktion (vgl. Abschnitt 3.3.2.0). Sie ist immer größer als 0, weshalb stets ein primitives Element existiert. Aus diesem Grund ist jede multiplikative ABEL’sche Gruppe zyklisch, mit 𝜙(|𝐺^∗|) Generatorelementen.¹⁴

2.1.5 Elemente als Nullstellen

Wenden wir uns jetzt einer etwas anderen Sichtweise auf die Elemente der multiplikativen Gruppe 𝐺^∗ zu, nämlich der Betrachtung über Nullstellen. Dazu gehen wir von dem Polynom 𝜑(𝑥) = 𝑥^|𝐺∗| −1 mit 𝑥,𝜑(𝑥) ∈ 𝐺^∗ aus, welches die Nullstellen bzw. Einheitswurzeln 𝛼 haben soll.

Wir stellen nun fest, daß entsprechend des Fundamentalsatzes der Algebra 𝜑(𝑥) genau |𝐺^∗| Nullstellen haben muß. Nach Formel 10 wird diese Bedingung aber auch durch jedes Element aus 𝐺^∗ erfüllt. Da deren Anzahl genau mit der Anzahl der Nullstellen übereinstimmt, kann es sich bei den Elementen 𝑟 ∈ 𝐺^∗ nur um die |𝐺^∗| Nullstellen von 𝜑(𝑥) handeln [25, Satz 6.18]. Das mehrfache Nullstellen nicht vorhanden sind, kann man (in Verbindung mit Gleichung 14) durch Ableitung von 𝜑(𝑥) an den Stellen 𝛼 nachprüfen.

Mit diesen Erkenntnissen läßt sich für 𝜑(𝑥) eine Linearfaktordarstellung auf Basis der Elemente 𝑟 angeben.

Ausmultiplizieren der rechten Seite führt mit 𝜑(0) = −1 noch zu der interessanten Äquivalenz:

Da alle Elemente 𝑟 der multiplikativen Gruppe 𝐺^∗ als Potenzen eines Generatorelements 𝑔 darstellbar sind, kann man die Linearfaktordarstellung 15 auch folgendermaßen schreiben:

2.2 Endliche Körper

2.2.1 Definition

Jeder endliche Körper ist durch eine beschränkte Anzahl von Elementen gekennzeichnet, auf welche die Körperaxiome von Abschnitt 1.3 zutreffen. Man nennt solche algebraischen Strukturen auch GALOIS-Körper und bezeichnet sie mit F_𝑞 oder GF(𝑞), wobei 𝑞 die Ordnung (Anzahl der Elemente) des Körpers angibt.¹⁵ Bei der Konstruktion eines endlichen Körpers ist von allergrößter Bedeutung, daß zu den Eigenschaften eines Ringes noch die der multiplikativen Gruppe kommen. Zusätzliches Kriterium ist danach die Existenz des multiplikativ inversen Elements 𝑟⁻¹ zu jedem 𝑟 ∈ F_𝑞^∗.

2.2.2 Ordnung

Definiert 𝑞 die Anzahl der Elemente im Körper, d. h. inklusive Nullelement 𝑒₍₊₎, dann muß für die Ordnung der multiplikativen Gruppe F_𝑞^∗ := F_𝑞 \{0} gelten:

(17)

Entsprechend Abschnitt 2.1.3 muß die Ordnung der multiplikativen Gruppe ein Vielfaches der Elementeordnung 𝑘 = |𝑟| sein: |F_𝑞^∗| = 𝑖𝑘 (Satz von LAGRANGE). Ein GALOIS-Körper kann deshalb nicht jede beliebige Ordnung annehmen – wegen vorgenannter Bedingung müssen 𝑞 = |F_𝑞^∗| + 1 und die Ordnung 𝑘 eines jeden Elements 𝑟 ∈ F_𝑞^∗ teilerfremd sein.¹⁶

Diese Erkenntnis läßt sich (einerseits logisch, aber auch rein analytisch) aus

mit Hilfe des Satzes von BéZOUT ableiten. Dazu vergleicht man Beziehung § mit Formel 37 aus Abschnitt 4.1.1 und stellt fest:

Die einfachste Möglichkeit Teilerfremdheit zu gewährleisten, ist die Wahl von 𝑞 als Primzahl oder als Potenz einer Primzahl. Im ersten Fall nennt man F_𝑝 einen Primzahlenkörper, für 𝑞 = 𝑝^𝑛 einen Erweiterungs- oder Binärkörper (weitere Ausführungen zu F_𝑝^𝑛 in Abschnitt 3.4).

2.2.3 Elemente als Nullstellen

Aus Abschnitt 2.1.5 (Gleichung 15) ist bekannt, daß man die Elemente der multiplikativen Gruppe F_𝑞^∗ als Nullstellen des Polynoms 𝜑(𝑥) = 𝑥^𝑞−1 −1 auffassen kann. Nimmt man jetzt noch das Nullelement 𝑒₍₊₎ = 0 hinzu, dehnt also die Betrachtung von der multiplikativen Gruppe auf alle Elemente des Körpers aus, dann kann man als zusätzlichen Linearfaktor 𝑥 −0 einbeziehen:

(20)

Deshalb bilden die Nullstellen von 𝑥^𝑞 −𝑥 = 𝑥(𝑥^𝑞−1 −1) einen endlichen Körper F_𝑞.