3 Restklassen

3.1 Definition

Restklassen sind Kongruenzen von Elementen (einer algebraischen Struktur) modulo eines fixen Elements 𝑚. Das Rechnen mit solchen Elementen wird als modulare oder Modulo-Arithmetik und 𝑚 als das Modul bezeichnet. In diesem Sinne definiert man

(21)

als den Rest 𝑟, der bei der „Division“ 𝑎/𝑚 entsteht und sagt: 𝑟 ist kongruent 𝑎 modulo 𝑚. Im Umkehrschluß sind die Restklassenelemente durch die Relation

(22)

bestimmt. Die Äquivalenzrelation 𝑟 ≡ 𝑎 mod 𝑚 kann man z. B. im Ring der ganzen Zahlen Z definieren, ist aber nicht auf diesen beschränkt. Im allgemeinen Fall 𝑎 ∈ 𝑅 schreibt man für die Restklasse

d. h. die Restklasse 𝑚 ist die Menge aller Elemente 𝑎 ∈ 𝑅, die bei der Division modulo 𝑚 genau den Rest 𝑟 ergeben. Ein Beispiel für 𝑎 ∈ Z mit einem Modul von 𝑚 = 4 soll das veranschaulichen.

Üblicherweise bezeichnet man die Menge aller Restklassen mit

also z. B. für die ganzen Zahlen 𝑎 ∈ Z modulo 𝑚:

Im Allgemeinen werden Verknüpfungsoperationen (Addition, Multiplikation usw.) zwischen zwei Restklassen dadurch definiert, daß man jeweils einen Vertreter aus den Restklassen auswählt und dann die Operation mit diesem Repräsentanten durchführt.

3.2 Restklassenringe

Um von einem Restklassenring (𝑅_𝑚,+,·) sprechen zu können ist der Nachweis aller Ringaxiome von Abschnitt 1.2 in Bezug auf die Menge der Restklassen 𝑅_𝑚 notwendig [34, S. 5.]. Dazu geht man von der Modulo-Arithmetik nach Gleichung 21 und 22 aus und prüft jeden Punkt durch Einzelbetrachtung:

1. Bezüglich der Addition muß (𝑅_𝑚,+,·) eine ABEL’sche Gruppe bilden, d. h.

   1. die Addition existiert und ist abgeschlossen;¹⁷

      

   2. sie ist außerdem sowohl assoziativ als auch kommutativ (ABEL’sch);

      

   3. das neutrale Element 𝑒₍₊₎ = 𝑚 = 𝑚𝑞₀ existiert;

      

   4. jedes Element besitzt ein inverses Element −𝑚 = (𝑚 −𝑎) mod 𝑚 mit

      

2. Für die Multiplikation muß (𝑅_𝑚,+,·) eine Halbgruppe darstellen, also

   1. ebenfalls abgeschlossen sein;

      

   2. und das Assoziativgesetz für 𝑚 ∈ 𝑅_𝑚 erfüllen;

      

3. Außerdem muß für alle 𝑚 ∈ 𝑅_𝑚 das Distributivgesetz erfüllt sein.
   

   

Da (𝑅_𝑚,·) ein neutrales Element 𝑒_(·) mit 𝑚 ·𝑒_(·) = 𝑚 besitzt, handelt es sich sogar um einen Ring mit Eins.

Aus Anwendungssicht ist sofort zu erkennen, daß insbesondere die Restklassen 𝑅_𝑚 = Z_𝑚 alle diese Bedingungen für 𝑚 ≥ 2 erfüllen und somit einen kommutativen Ring mit Einselement bilden.

3.3 Restklassenkörper

3.3.1 Existenz

Für den Übergang von einem Restklassenring (𝑅_𝑚,+,·) zu einem Restklassenkörper muß man zu jedem 𝑟 ∈ 𝑅_𝑚 \ {0} das Vorhandensein eines multiplikativ inversen Elements 𝑚⁻¹, mit 𝑚 ·𝑚⁻¹ = 𝑚 , fordern. Wir nehmen die Antwort vorweg und proklamieren, daß es ein solches Element in (𝑅_𝑚,+,·) nur dann gegeben kann, wenn 𝑚 und 𝑟 teilerfremd sind [25, Satz 6.4]. Bezieht man diese Aussage z. B. auf Z_𝑚^∗ = Z_𝑚 \{0} = {1,2,3,…,𝑚−1}, dann müssen (wenn keine weiteren Forderungen an 𝑚 gestellt werden) alle Elemente 𝑟, für die gcd(𝑟,𝑚) = 1 nicht erfüllt werden kann, ausgeschlossen werden. Sowohl im allgemeinen als auch speziellen Fall von Z_𝑚^∗ ist diese Einschränkung grundsätzlich hinfällig, wenn es sich bei 𝑚 um ein Primelement handelt (ein vollständiges Restklassensystem) – in Bezug auf Z_𝑚^∗ also um eine Primzahl 𝑝 ∈ P, weshalb F_𝑞 := Z_𝑝 (mit 𝑞 = 𝑝). Im Fall des Ausschlusses von Elementen (ein reduziertes Restklassensystem) ist die Anzahl der teilerfremden Zahlen durch EULER’s Totient-Funktion 𝜙(𝑚) bestimmt und so die Ordnung der multiplikativen Gruppe |Z_𝑚^∗| = 𝜙(𝑚), d. h. F_𝑞 ⊆ Z_𝑚 (mit 𝑞 = 𝜙(𝑚) +1).

Beweis Ist 𝑚 kein primes Element, dann läßt es sich mindestens in zwei Faktoren 𝑟,𝑠 ∈ 𝑅_𝑚 zerlegen (die nicht Vielfache von 𝑚 sind, also 𝑟,𝑠 mod 𝑚 ≠ 0). Da nun 𝑚 mod 𝑚 = 0 ist, gilt für die Restklassenmultiplikation 𝑚 ·𝑚 = 𝑚 = 0. Soll aber 𝑚 eine inverse Restklasse 𝑚⁻¹ besitzen, dann kann man beide Seiten des Produktes mit 𝑚⁻¹ multiplizieren.

𝑚 ist aber nach Voraussetzung nicht 0, demzufolge kann ein Inverses zu 𝑚 für den Fall dieser Zerlegung nicht existieren.

Im Gegenzug bleibt noch nachzuweisen, daß, wenn 𝑚 ein Primelement ist, für jede Restklasse 𝑚 aus 𝑅_𝑚 ein inverses Element 𝑚⁻¹ auch wirklich existiert. Zu diesem Zweck betrachten wir alle 𝑚 ∈ 𝑅_𝑚, ausgenommen die Restklasse 𝑚 , welche bei der Inversion auf sich selbst abgebildet wird. Da wegen der Modulo-Reduktion (wir verwenden jetzt wieder den Vertreter der Restklasse) immer 𝑚 > 𝑟 gilt, kann nur 𝑟 ein Teiler von 𝑚 sein und nicht umgekehrt. Aber auch dies ist nicht möglich, wenn nach Voraussetzung 𝑚 relativ prim zu 𝑟 ist. Deshalb kann der größte gemeinsame Teiler von 𝑟 und 𝑚 nur das Einselement sein. Berücksichtigt man jetzt noch die aus dem euklidischen Algorithmus stammende Erkenntnis (Satz von BéZOUT, vgl. Abschnitt 4.1), daß der größte gemeinsame Teiler 𝑑 = gcd(𝑟,𝑠) zweier Elemente 𝑟,𝑠 in der Form 𝑑 = 𝛼𝑟+𝛽𝑠 mit 𝛼,𝛽 ∈ Z darstellbar ist, dann gilt:

Das inverse Element von 𝑚 ist demzufolge

wobei dessen Berechnung z. B. mit Hilfe des erweiterten euklidischen Algorithmus (siehe Abschnitt 4.1.4) möglich ist.¹⁸

3.3.2 Multiplikative Gruppe

Da es sich bei den Restklassenkörpern um spezifische GALOIS-Körper handelt, kann man einige Formeln von Abschnitt 2.2 konkretisieren. Im folgenden sollen deshalb die Körperelemente und deren Ordnung im Zusammenhang mit der multiplikativen Gruppe F_𝑞^∗ betrachtet werden.

Ordnung von Elementen Abgesehen von den allgemein geltenden Ordnungsrelationen (siehe Abschnitt 2.1) gibt es speziell für den Restklassenkörper Z_𝑝 noch eine erwähnenswerte Ausdrucksmöglichkeit für die von einem Körperelement generierte zyklische Untergruppe:

(24)

Einsichtig wird die Schreibweise sofort, wenn man sie für jeden Exponent 𝑛 expandiert.¹⁹

Kleiner Satz von Fermat Eine für die praktische Anwendung von Restklassenkörpern sehr wichtige Folgerung aus Gleichung 11 ist der (für den Restklassenkörper Z_𝑝 geltende) kleine Satz von FERMAT [26, S. II]. Er resultiert sofort aus 𝑟^𝑞−1 ≡ 1 (mod 𝑚), wenn man berücksichtigt, daß die Ordnung der multiplikativen Gruppe Z_𝑝^∗ = Z_𝑝 \ {0} = {1,2,3,…,𝑝 − 1} genau 𝑞 − 1 = 𝑝 − 1 ist.

(25)

Aus dieser Kongruenz kann man wegen 0 ≡ 𝑝 (mod 𝑝) außerdem ableiten, daß 𝑝 stets ein Teiler von 𝑟^𝑝−1 −1 ist.²⁰

(26)

Obwohl der kleine Satz von FERMAT ursprünglich auf Z_𝑝 bezogen war, wird sein Name oft auch in Verbindung mit Ausgangsformel 11 verwendet (siehe zum Beispiel [9]) — also ganz allgemein bezogen auf den endlichen Körper F_𝑞. Deshalb sollen an dieser Stelle noch weitere Berechnungsmöglichkeiten erwähnt sein, welche sich direkt aus 𝑟^𝑞−1 = 1 ergeben.

1. Multiplikation mit 𝑟⁻¹ führt z. B. zur Möglichkeit ein Element zu invertieren.

   

2. Multiplikation mit 𝑟² gibt uns eine weitere Ausdrucksmöglichkeit für das Quadrat eines Elements.

   

3. Für einige Spezialfälle ermöglicht der kleine Satz von FERMAT sogar das Ziehen der Quadratwurzel aus einem Element.

   1. Beispielsweise kann man im Erweiterungskörper F_2^𝑛 (vgl. Abschnitt 3.4), in welchem 𝑞 = 2^𝑛 ja immer gerade ist, direkt folgende Formel angeben:

      

   2. Aber auch im Körper F_𝑝 kann man, zumindest für den Fall 𝑝 ≡ 3 mod 4, eine einfache Lösung präsentieren:²¹

      

      Mit einer kurzen Probe läßt sie sich schnell verifizieren:

      

Satz von Wilson Betrachtet man die multiplikative Gruppe eines Restklassenkörpers Z_𝑝>2 , so handelt es sich bei den Zahlen 𝑟 = 1,2,…,𝑝−1 um die 𝑝−1 Nullstellen 𝛼 des Polynoms 𝜑(𝑥) = 𝑥^𝑝−1 −1 (mod 𝑝). Anwendung von Gleichung 16 auf Z_𝑝^∗ führt folgerichtig zum Satz von WILSON [31, S. 2.8.1], [26, S. II], [6, S. 2].²²

(27)

Satz von EULER L. EULER hat für natürliche Zahlen eine sogenannte Totient-Funktion 𝜙(𝑚) definiert, welche die Anzahl der positiven Zahlen (größer als 0 und kleiner als 𝑚) teilerfremd zu 𝑚 ausdrückt.²³ Mit Hilfe dieser Funktion hat er FERMAT’s kleinen Satz folgendermaßen verallgemeinert [31, S. 2.6], [6, S. 2], [26, S. II]:

Sind zwei Zahlen 𝑟,𝑚 ∈ N relativ prim zueinander, d. h. sie haben keinen gemeinsamen Teiler (und so ist gcd(𝑟,𝑚) = 1), dann gilt:

(28)

Der Beweis ist mit den Betrachtungen von Abschnitt 2.1 zur Ordnung der multiplikativen Gruppe in Z_𝑚 zu erbringen. Danach entspricht die Gruppenordnung |Z_𝑚^∗| der Anzahl invertierbarer Elemente (solche mit gcd(𝑟,𝑚) = 1), d. h. mit EULER’s Totient-Funktion genau |Z_𝑚^∗| = 𝜙(𝑚).²⁴ Berücksichtigt man jetzt noch die Gruppen nach Formel 11, dann bestätigt sich EULER’s Satz in Form von Gleichung 10.

Speziell im Restklassenkörper Z_𝑝 entspringt aus Kongruenz 28 mit 𝜙(𝑝) = |Z_𝑝^∗| = 𝑝−1 sofort der kleine Satz von FERMAT.

Für einen speziellen Fall, nämlich das Produkt zweier Primzahlen 𝑚 = 𝑝𝑞, ist es sehr wünschenswert die Totient-Funktion zu kennen.²⁵ Sind 𝑝 und 𝑞 nach Voraussetzung Primzahlen, dann können nur die Zahlen (kleiner als 𝑚) gemeinsame Teiler mit 𝑚 haben, die Vielfache von 𝑝 oder 𝑞 sind. Vielfache von 𝑝 die kleiner als 𝑚 sind, gibt es aber genau 𝑞−1, was für 𝑞 äquivalent gilt (nämlich 𝑝,2𝑝,3𝑝,…,(𝑞−1)𝑝 und 𝑞,2𝑞,3𝑞,…,(𝑝−1)𝑞). Somit muß man von den 𝑚−1 Zahlen kleiner als 𝑚 genau 𝑝−1 +𝑞−1 = 𝑝+𝑞−2 subtrahieren, was zu

führt.²⁶ In ähnlicher Art und Weise kann man auch die folgende Formel ableiten:

3.3.3 Beispiele

Körper Z₂ Der Körper F₂ := Z₂ ist von besonderer praktischer Bedeutung, denn er bildet häufig die Grundlage technischer Realisierungen. Die beiden Elemente von Z₂ werden mit {2,2} oder kürzer mit 0,1 bezeichnet. Wegen ihrer einfachen Implementierung sind die Operationen in Z₂ besonders effizient.

1. Die Addition (modulo 2) ist mit
   

   

   geradezu primitiv und entspricht dem logischen Exklusiv-Oder.²⁷ Wie man sofort sieht, ist das neutrale Element die 0 und wegen Beziehung 29 das additiv Inverse die 1. Addition und Subtraktion sind in diesem Sinne gleichwertig, denn es gilt −1 ≡ 1 (mod 2).

2. Ebenfalls eine einfache Operation ist die Multiplikation, denn sie entspricht dem logischen Und.
   

   
3. Die Division erklärt sich mit Hilfe des inversen Elements in Z₂^∗ = Z₂ \{0} = {1}, welches ja die Bedingung 1 ·1⁻¹ = 𝑒_(·) = 1 erfüllen muß. Einzig mögliche Schlußfolgerung ist die, daß es sich bei dem inversen Element 1⁻¹ um 1 selbst handelt.

Körper Z₅ Für den Körper Z₅, also dem Fall einer multiplikativen Gruppe der |Z₅^∗| = 𝑞−1 = 4, gilt für die Elemente:

3.4 Erweiterungskörper

3.4.1 Vorbetrachtungen

Ein Erweiterungskörper 𝑀/𝐾 ist ein Körper (𝑀,+,·), der einen anderen Körper (𝐾,+,·) als Teilkörper enthält [25, S. 6.5]. Der Grad der Körpererweiterung von 𝑀 über 𝐾 ist die Dimension von 𝑀 als (so genannter) 𝐾-Vektorraum und wird als [𝑀 : 𝐾] bzw. dim _𝐾 𝑀 geschrieben. Jeder Vektor in 𝑀 besteht entsprechend der Definition des Vektorraumes (vgl. Abschnitt 1.4) aus jeweils [𝑀 : 𝐾] Tupeln in 𝐾. Bekannte Beispiele für Körpererweiterungen sind:

3.4.2 Polynomringe

Ausgehend von den Vorbetrachtungen konstruieren wir jetzt einen endlichen Polynomring (𝐾[𝑥],+,·) auf dem Körper 𝐾.

Darin seien die üblichen Polynomoperationen, wie Addition und Multiplikation gültig, weshalb man auch von einem Vektorraum der Polynome in der Unbestimmten 𝑥 mit Koeffizienten aus dem Körper 𝐾 spricht. Ist der Leitkoeffizient 𝑎_𝑛−1 = 1, dann wird das Polynom als normiert (monisch) bezeichnet, sonst ist 𝑎_𝑛−1𝑥^𝑛−1 das so genannte Leitmonom.

Wird anschließend eine Restklassendivision dieser Polynome 𝑓(𝑥) durch ein Polynom 𝑚(𝑥) mit Grad 𝑛 definiert, also 𝑟(𝑥) = 𝑓(𝑥) mod 𝑚(𝑥) mit 𝑟(𝑥) ∈ 𝐾[𝑥]/𝑚(𝑥), dann bildet die Menge der darin enthaltenen Restklassen wieder einen Restklassenring [25, S. 6.], [22, S. 2.5.4].

Der Polynom-Restklassenring auf dem Grundkörper Z_𝑝 Im Beispiel des Restklassenringes Z_𝑝[𝑥]/𝑚(𝑥) lassen sich die Eigenschaften eines Ringes (siehe Abschnitt 1.2) wiefolgt nachweisen:

1. Da bei einer Polynomaddition die einzelnen Koeffizienten unabhängig voneinander (und jeder für sich) addiert werden und außerdem nach Voraussetzung immer deg 𝑟(𝑥) < deg 𝑚(𝑥) = 𝑛 gilt, bildet 𝐾[𝑥]/𝑚(𝑥) eine additive ABEL’sche Gruppe.

   1. Das Assoziativgesetz gilt: 𝑟(𝑥) + = + ℎ(𝑥) mit 𝑟(𝑥),𝑔(𝑥),ℎ(𝑥) ∈ 𝐾[𝑥]/𝑚(𝑥).
   2. Das neutrale Element 𝑒₍₊₎ = 0 ∈ 𝐾/𝑚(𝑥) mit der Beziehung 𝑟(𝑥)+𝑒₍₊₎ = 𝑟(𝑥) ist das Nullpolynom.
   3. Ein additiv inverses Element −𝑟 ∈ 𝐾/𝑚(𝑥) mit 𝑟 + = 0 ist vorhanden. Es ergibt sich aus den inversen Elementen der Koeffizienten 𝑎_𝜈 ∈ 𝐾 zu −𝑟(𝑥) = ∑ _𝜈=0^𝑛−1 −𝑎_𝜈𝑥^𝜈 = −∑_𝜈=0^𝑛−1𝑎_𝜈𝑥^𝜈.

2. (𝐾[𝑥]/𝑚(𝑥),·) ist eine multiplikative Halbgruppe, denn:

   1. Aufgrund der Modulo-Reduktion ist (𝐾[𝑥]/𝑚(𝑥),·) abgeschlossen, d. h. wenn 𝑟(𝑥),𝑔(𝑥) ∈ 𝐾[𝑥]/𝑚(𝑥) angenommen wird, dann gilt für die Multiplikation 𝑟(𝑥)𝑔(𝑥) ≡ ℎ(𝑥) (mod 𝑚(𝑥)) gleichfalls ℎ(𝑥) ∈ 𝐾[𝑥]/𝑚(𝑥).
   2. Auch das Assoziativgesetz 𝑟(𝑥) = ℎ(𝑥) ist in einem Restklassenring von Polynomen erfüllt.
3. Aus den bisherigen Erkenntnissen zu Restklassenringen ist im Zusammenhang mit Polynomoperationen zu schlußfolgern, daß das Distributivgesetz ebenfalls gilt: 𝑟(𝑥) = 𝑟(𝑥)𝑔(𝑥) +𝑟(𝑥)ℎ(𝑥).

3.4.3 Endlicher Erweiterungskörper

Der Übergang zu einem Körper wird möglich, wenn 𝑚(𝑥) ein Primelement in Bezug auf die Menge der Polynome 𝐾[𝑥] ist, es sich also um ein (so genanntes) irreduzibles Polynom handelt. Ein solches Polynom ist dadurch gekennzeichnet, daß es nicht weiter in Teilpolynome mit Koeffizienten aus 𝐾 reduzierbar ist.²⁸

Es sei nun 𝑟(𝑥) ein Restklassenpolynom mit Koeffizienten 𝑎 aus dem endlichen Grundkörper 𝐾 := F_𝑝 und 𝑚(𝑥) vom Grad 𝑛. Dann handelt es sich bei F_𝑝[𝑥]/𝑚(𝑥) um einen endlichen Körper mit 𝑞 = 𝑝^𝑛 Elementen [4, S. 3.8]. Man spricht auch von einem Vektorraum 𝑉 der Dimension 𝑛 über F_𝑝, denn auf diese Weise wird (im Sinne von Abschnitt 1.4) jedem Vektor v = (𝑣₁,𝑣₂,𝑣₃,…,𝑣_𝑛) ein Polynom 𝑟(𝑥) vom Grad 𝑛−1 zugeordnet. Es handelt sich folglich nur um eine andere Darstellung der 𝑛 Tupel des Vektors v in der Art 𝑎₀ = 𝑣₁,𝑎₁ = 𝑣₂,…,𝑎_𝑛−1 = 𝑣_𝑛. Die Potenzen 𝑥⁰,𝑥¹,𝑥²,…,𝑥^𝑛−2,𝑥^𝑛−1 bilden die (Polynom-) Basis des Vektorraumes 𝑉 über F_𝑝. Entsprechend ist die Dimension des Erweiterungskörpers F_𝑞 über dem Grundkörper F_𝑝 genau [F_𝑞 : Z_𝑝] = 𝑛. Als Notation für einen solchen Körper wird deshalb auch F_𝑝^𝑛 oder GF(𝑝^𝑛) verwendet.

Mit diesen Vorbemerkungen lassen sich alle Aussagen zu Restklassenkörpern, wie sie in Abschnitt 3.3 allgemein formuliert wurden, auf den Erweiterungskörper F_{𝑞=𝑝^𝑛} anwenden:

1. Das Modul 𝑚 (Primelement) wird nun als das irreduzible Polynom 𝑚(𝑥) interpretiert.
2. Die Restklassendivision ist definiert als 𝑟(𝑥) ≡ 𝑓(𝑥) mod 𝑚(𝑥), was grundsätzlich immer zu einem Grad kleiner als 𝑛 für 𝑟(𝑥) führt.²⁹ Die Kennzeichnung der zu 𝑟(𝑥) gehörenden Restklasse erfolgt wie gewohnt mit 𝑚(𝑥) , wird meistens jedoch weggelassen. Das Element 𝑟(𝑥) steht also auch hier wieder als Restklassenvertreter aller Polynome 𝑓(𝑥), welche die Bedingung 𝑓(𝑥) = 𝑠(𝑥)𝑚(𝑥)+𝑟(𝑥) mit deg 𝑟(𝑥) < deg 𝑚(𝑥) erfüllen.
3. Das Nullelement ist das Nullpolynom 𝑟(𝑥) = 0 (mod 𝑚(𝑥)) bzw. dessen Restklasse 𝑚(𝑥) , das Einselement das Einheitspolynom 𝑒_(·) = 𝑥⁰ = 1.
4. Addition und Multiplikation (von Polynomen) in F_𝑞 sind wohldefiniert und abgeschlossen, die entsprechenden Gruppen F_𝑞^∗ und F_𝑞⁺ also existent.
5. Die Anzahl der Elemente 𝑟(𝑥) im Restklassenkörper F_𝑝[𝑥]/𝑚(𝑥) ist aufgrund der Anzahl von möglichen Koeffizientenkombinationen 𝑝^𝑛. Bei F_𝑞 handelt es sich folglich um einen GALOIS-Körper GF(𝑝^𝑛).³⁰ Wegen |F_𝑞| = 𝑞 = 𝑝^𝑛 hat dessen multiplikative Gruppe F_𝑞^∗ die Ordnung 𝑝^𝑛 −1.

6. Jedes Element 𝑟(𝑥) ∈ F_𝑞^∗ hat eine Ordnung bzw. Periode 𝑘 = , welche sich aus Gleichung 2 ableitet:

   

7. Nach dem Satz von LAGRANGE teilt die Ordnung 𝑘 des Elements die der multiplikativen Gruppe F_𝑞^∗, d. h. 𝑞−1 = 𝑝^𝑛 −1 = 𝑖𝑘 und demzufolge ist

   (32)

8. Jedes erzeugende Element 𝑔(𝑥) von F_𝑞^∗ erfüllt die Bedingung der maximalen Zykluslänge (Index 𝑖 = 1), hat also die Ordnung = 𝑝^𝑛 −1. Es ist damit geeignet, als Basiselement für die Erzeugung aller anderen Elemente 𝑟(𝑥) ∈ F_𝑞^∗ verwendet zu werden. Nimmt man das Nullelement 0 = 𝑔^𝑞 sowie das Einselement 1 = 𝑔^𝑞−1 hinzu, so gilt für die Menge der Elemente F_𝑞 = {0,1,𝑔¹,𝑔²,𝑔³,…,𝑔^𝑝𝑛−3 ,𝑔^𝑝𝑛−2 }.

9. Aus Punkt 6 läßt sich (in Übereinstimmung mit Gleichung 26) schlußfolgern, daß für jedes Element 𝑟(𝑥) ∈ F_𝑞^∗ das Modul 𝑚(𝑥) ein Teiler von ^𝑞−1 − 1 ist, also die Zerlegung ^𝑞−1 − 1 = ℎ(𝑥)𝑚(𝑥) hat. Setzt man insbesondere 𝑟(𝑥) = 𝑥 als das kleinste Element (mit einem Grad größer als 0) aus F_𝑞^∗, so erhält man die Beziehungen:

   

   welche auch die Kongruenz ℎ(𝑥)𝑚(𝑥) ≡ 0 (mod 𝑥^𝑞−1 −1) rechtfertigen.

3.4.4 Zerfällungskörper

Nach dem Hauptsatz der Zahlentheorie kann man für jede natürliche Zahl eine eindeutigen Primfaktorzerlegung der Form

finden. Gleiches trifft auch für Polynome in F_𝑝[𝑥] zu, nur daß es sich um irreduzible Polynome anstatt Primzahlen handelt.

Jedes der irreduziblen Polynome³¹ 𝑚_𝑖(𝑥) hat eine vom jeweiligen Grad 𝑛 abhängige Anzahl von Nullstellen 𝛼, die entweder im Grundkörper F_𝑝 oder (sämtlich) in einem zugehörigen Erweiterungskörper F_𝑝^𝑛 liegen. Nullstellen im Grundkörper, von denen 𝑓(𝑥) maximal 𝑝 = |F_𝑝| besitzen kann, lassen sich immer als einfache Faktoren der Art 𝑚(𝑥) = 𝑥 − 𝛼 mit 𝛼 ∈ F_𝑝 darstellen (vgl. Beispiel-Faktorisierung von 𝑥³ −1 in Abschnitt 3.4.5). Liegen dagegen alle 𝑛 Wurzeln von 𝑚(𝑥) in einem Erweiterungskörper, dann muß es sich um ein irreduzibles Polynom (höheren Grades) handeln.³² Ein solcher Körper besteht aus 𝑝^𝑛 Elementen, welche die 𝑞 = 𝑝^𝑛 Nullstellen der zugeordneten Funktion 𝜓(𝑥) = 𝑥^𝑞 −𝑥 darstellen (vgl. Abschnitt 2.1.5). F_𝑝^𝑛 nennt man deshalb auch den kleinsten Körper über den 𝜓(𝑥) ∈ F_𝑝[𝑥] vollständig in Linearfaktoren zerfällt [4, S. 4.5] bzw. kürzer: F_𝑝^𝑛 sei der Zerfällungskörper von 𝑥^𝑞 −𝑥.

Ein weiteres Charakteristikum des Zerfällungskörpers F_𝑝^𝑛 sind die konjugierten Nullstellen, d. h. bei Kenntnis einer Nullstelle 𝛼 ≠ 0 des irreduziblen Polynoms 𝑚(𝛼) = 0 sind die restlichen 𝑛 −1 Nullstellen genau die Potenzen 𝛼^𝑝,𝛼^𝑝2 ,…,𝛼^𝑝𝑛−2 ,𝛼^𝑝𝑛−1 . Das irreduzible Polynom 𝑚(𝑥) zerfällt also bei Kenntnis nur einer Nullstelle 𝛼 vollständig in seine 𝑛 Linearfaktoren. Der Beweis dieses Satzes geht vom sogenannten „Anfänger-Traum“ (Freshmans Dream) aus:

(33)

und berücksichtigt dann, daß im Grundkörper F_𝑝 jedes Element 𝑎 die Relation 𝑎^𝑝 = 𝑎 erfüllt (vgl. Abschnitt 3.3.2).

Aus diesem Grund läßt sich für jedes der irreduziblen Polynome 𝑚(𝑥) die folgende Linearfaktordarstellung angeben:³³

Die Nullstellen 𝛼^𝑝𝑖 kann man (wegen ihrer linearen Unabhängigkeit) verwenden, um statt einer Polynombasis eine so genannte Normalbasis des Vektorraumes (der Dimension 𝑛) über F_𝑝 zu definieren.

Ergänzungen zu Formel 33

1. Sie kommt zustande wenn man bei der formalen Anwendung des Binomischen Satzes berücksichtigt, daß im Binomialkoeffizient = der Faktor 𝑝! für 𝑘 ≠ 0 immer durch 𝑝 teilbar ist und folglich mod 𝑝 = 0 gilt.

   

2. Wendet man sie mehrfach an, dann ergibt:

   (34)

3.4.5 Erweiterungskörper Z₂^𝑛

Für eine Erweiterung des Primkörpers Z₂ auf 𝑛 Dimensionen ist ein irreduzibles Polynom 𝑚(𝑥) vom Grad 𝑛 notwendig. Der dadurch entstehende Körper Z₂^𝑛 soll am Beispiel des Polynoms 𝑚(𝑥) = 𝑥² +𝑥 +1 mit Koeffizienten aus Z₂ (zu den Rechenoperationen vgl. Seite §) jetzt kurz betrachtet werden. Nach Darstellung 30 gehören genau 𝑞 = 𝑝^𝑛 = 4 Polynome zum Erweiterungskörper (𝑝 = 2, 𝑛 = 2), nämlich:

Wie sich leicht feststellen läßt, ist 𝑟₃(𝑥) das erzeugende Element der multiplikativen Gruppe , denn die anderen Elemente ergeben sich als Potenzen 𝑟₃^𝜈(𝑥) mod 𝑚(𝑥).

Außerdem sind alle Elemente (abgesehen von 𝑟₀(𝑥)) wirklich Nullstellen des Polynoms 𝑥^𝑞−1 −1 = 𝑥³ −1 = (𝑥−1)𝑚(𝑥). Auch gut erkennen läßt sich, daß 𝑚(𝑥) für jedes Element 𝑟(𝑥) ein Teiler von ^𝑞−1 −1 ist.

Äquivalent dazu ist das Produkt aller Elemente (konform zu Formel 16) genau das neutrale Element 𝑒_(·) der multiplikativen Gruppe.³⁴