Erweiterungskorper

3.4 Erweiterungskörper

3.4.1 Vorbetrachtungen

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

3.4.2 Polynomringe

Ausgehend von den Vorbetrachtungen konstruieren wir jetzt einen endlichen Polynomring $(K[x],+,⋅)$ auf dem Körper $K$ .

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

Wird anschließend eine Restklassendivision dieser Polynome $f(x)$ durch ein Polynom $m(x)$ mit Grad $n$ definiert, also $r(x)= f(x) mod m (x)$ mit $r(x)∈ K [x]∕m(x)$ , dann bildet die Menge der darin enthaltenen Restklassen wieder einen Restklassenring [PW72, 6.], [MvV92, 2.5.4].

Der Polynom-Restklassenring auf dem Grundkörper $ℤp$ Im Beispiel des Restklassenringes $ℤp [x]∕m(x)$ lassen sich die Eigenschaften eines Ringes (siehe Abschnitt 1.2) wiefolgt nachweisen:

Da bei einer Polynomaddition die einzelnen Koeffizienten unabhängig voneinander (und jeder für sich) addiert werden und außerdem nach Voraussetzung immer gilt, bildet eine additive ABEL’sche Gruppe.
1. Das Assoziativgesetz gilt: $r(x)+ [g(x)+ h(x)]= [r(x) +g (x)]+ h(x)$ mit $r(x),g(x),h(x) ∈ K[x]∕m (x)$ .
2. Das neutrale Element $e(+) = 0 ∈ K[x]∕m(x)$ mit der Beziehung $r(x)+ e(+) = r(x)$ ist das Nullpolynom.
3. Ein additiv inverses Element $− r(x)∈ K [x]∕m (x)$ mit $r(x)+ [− r(x)]= 0$ ist vorhanden. Es ergibt sich aus den inversen Elementen der Koeffizienten $a ∈ K ν$ zu $n− 1 ν n−1 ν − r(x)= ∑ ν=0− aνx = − ∑ν=0 aνx$ .
ist eine multiplikative Halbgruppe, denn:
1. Aufgrund der Modulo-Reduktion ist $(K [x]∕m(x),⋅)$ abgeschlossen, d. h. wenn $r(x),g(x)∈ K [x]∕m(x)$ angenommen wird, dann gilt für die Multiplikation $r(x)g (x) ≡ h(x) (mod m (x))$ gleichfalls $h(x)∈ K[x]∕m (x)$ .
2. Auch das Assoziativgesetz $r(x)[g(x)h(x)]= [r(x)g(x)]h(x)$ ist in einem Restklassenring von Polynomen erfüllt.
Aus den bisherigen Erkenntnissen zu Restklassenringen ist im Zusammenhang mit Polynomoperationen zu schlußfolgern, daß das Distributivgesetz ebenfalls gilt: $r(x)[g(x) +h (x)]= r(x)g(x)+ r(x)h(x)$ .

3.4.3 Endlicher Erweiterungskörper

Der Übergang zu einem Körper wird möglich, wenn $m(x)$ ein Primelement in Bezug auf die Menge der Polynome $K [x]$ 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 $K$ reduzierbar ist.²⁹

Es sei nun $r(x)$ ein Restklassenpolynom mit Koeffizienten $a$ aus dem endlichen Grundkörper $K := F p$ und $m (x)$ vom Grad $n$ . Dann handelt es sich bei $F [x]∕m (x) p$ um einen endlichen Körper mit $n q = p$ Elementen [Bos96, 3.8]. Man spricht auch von einem Vektorraum $V$ der Dimension $n$ über $Fp$ , denn auf diese Weise wird (im Sinne von Abschnitt 1.4) jedem Vektor $v = (v1,v2,v3,...,vn)$ ein Polynom $r(x)$ vom Grad $n− 1$ zugeordnet. Es handelt sich folglich nur um eine andere Darstellung der $n$ Tupel des Vektors $v$ in der Art $a0 = v1,a1 = v2,...,an−1 = vn$ . Die Potenzen $x0,x1,x2,...,xn−2,xn−1$ bilden die (Polynom-) Basis des Vektorraumes $V$ über $Fp$ . Entsprechend ist die Dimension des Erweiterungskörpers $Fq$ über dem Grundkörper $Fp$ genau $[Fq :ℤp ]= n$ . Als Notation für einen solchen Körper wird deshalb auch $Fpn$ oder $GF (pn)$ verwendet.

Mit diesen Vorbemerkungen lassen sich alle Aussagen zu Restklassenkörpern, wie sie in Abschnitt 3.3 allgemein formuliert wurden, auf den Erweiterungskörper $Fq=pn$ anwenden:

Das Modul $m$ (Primelement) wird nun als das irreduzible Polynom $m(x)$ interpretiert.
Die Restklassendivision ist definiert als $r(x)≡ f (x) mod m(x)$ , was grundsätzlich immer zu einem Grad kleiner als $n$ für $r(x)$ führt.³⁰ Die Kennzeichnung der zu $r(x)$ gehörenden Restklasse erfolgt wie gewohnt mit $[r(x)] m(x)$ , wird meistens jedoch weggelassen. Das Element $r(x)$ steht also auch hier wieder als Restklassenvertreter aller Polynome $f(x)$ , welche die Bedingung $f(x)= s(x)m(x)+ r(x)$ mit $degr(x)< degm (x)$ erfüllen.
Das Nullelement ist das Nullpolynom $r(x) = 0 (mod m(x))$ bzw. dessen Restklasse $[0]m(x)$ , das Einselement das Einheitspolynom $e(⋅) = x0 = 1$ .
Addition und Multiplikation (von Polynomen) in $Fq$ sind wohldefiniert und abgeschlossen, die entsprechenden Gruppen $F∗q$ und $F+q$ also existent.
Die Anzahl der Elemente $r(x)$ im Restklassenkörper $Fp[x]∕m (x)$ ist aufgrund der Anzahl von möglichen Koeffizientenkombinationen $pn$ . Bei $Fq$ handelt es sich folglich um einen GALOIS-Körper $GF(pn)$ .³¹ Wegen $|F |= q= pn q$ hat dessen multiplikative Gruppe $F∗ q$ die Ordnung $pn− 1$ .
Jedes Element $r(x)∈ F∗q$ hat eine Ordnung bzw. Periode $k= |〈r(x)〉|$ , welche sich aus Gleichung 2.1 ableitet: $[r(x)]k − 1 ≡ 0 (mod m (x)).$
Nach dem Satz von LAGRANGE teilt die Ordnung $k$ des Elements die der multiplikativen Gruppe $∗ F q$ , d. h. $n q − 1= p − 1= ik$ und demzufolge ist
$[r(x)]q−1− 1≡ 0 (mod m(x)).$ (3.12)
Jedes erzeugende Element $g(x)$ von $F∗q$ erfüllt die Bedingung der maximalen Zykluslänge (Index $i= 1$ ), hat also die Ordnung $|〈g(x)〉|= pn − 1$ . Es ist damit geeignet, als Basiselement für die Erzeugung aller anderen Elemente $r(x) ∈F ∗ q$ verwendet zu werden. Nimmt man das Nullelement $q 0 = g$ sowie das Einselement $q−1 1= g$ hinzu, so gilt für die Menge der Elemente $1 2 3 pn−3 pn−2 Fq = {0,1,g ,g ,g ,...,g ,g }$ .
Aus Punkt 6 läßt sich (in Übereinstimmung mit Gleichung 3.6) schlußfolgern, daß für jedes Element $∗ r(x)∈ Fq$ das Modul $m(x)$ ein Teiler von $q−1 [r(x)] − 1$ ist, also die Zerlegung $q−1 [r(x)] − 1 = h(x)m (x)$ hat. Setzt man insbesondere $r(x) = x$ als das kleinste Element (mit einem Grad größer als $0$ ) aus $F∗q$ , so erhält man die Beziehungen:

welche auch die Kongruenz $h(x)m(x)≡ 0 (mod xq−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

me11me22me33⋅⋅⋅

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

f(x)= [m1(x)]e1 [m2 (x)]e2[m3 (x)]e3⋅⋅⋅

Jedes der irreduziblen Polynome³² $mi(x)$ hat eine vom jeweiligen Grad $n$ abhängige Anzahl von Nullstellen $α$ , die entweder im Grundkörper $F p$ oder (sämtlich) in einem zugehörigen Erweiterungskörper $F n p$ liegen. Nullstellen im Grundkörper, von denen $f(x)$ maximal $p = |Fp |$ besitzen kann, lassen sich immer als einfache Faktoren der Art $m (x)= x− α$ mit $α ∈Fp$ darstellen (vgl. Beispiel-Faktorisierung von $x3− 1$ in Abschnitt 3.4.5). Liegen dagegen alle $n$ Wurzeln von $m(x)$ in einem Erweiterungskörper, dann muß es sich um ein irreduzibles Polynom (höheren Grades) handeln.³³ Ein solcher Körper besteht aus $n p$ Elementen, welche die $n q = p$ Nullstellen der zugeordneten Funktion $q ψ (x)= x − x$ darstellen (vgl. Abschnitt 2.1.5). $Fpn$ nennt man deshalb auch den kleinsten Körper über den $ψ (x)∈ Fp[x]$ vollständig in Linearfaktoren zerfällt [Bos96, 4.5] bzw. kürzer: $Fpn$ sei der Zerfällungskörper von $xq− x$ .

ψ(x)= xq− x = ∏ (x − α ), ψ(x)∈ Fp[x] α∈Fq

Ein weiteres Charakteristikum des Zerfällungskörpers $Fpn$ sind die konjugierten Nullstellen, d. h. bei Kenntnis einer Nullstelle $α ⁄= 0$ des irreduziblen Polynoms $m(α )= 0$ sind die restlichen $n − 1$ Nullstellen genau die Potenzen $αp,αp2,...,αpn−2,αpn−1$ . Das irreduzible Polynom $m(x)$ zerfällt also bei Kenntnis nur einer Nullstelle $α$ vollständig in seine $n$ Linearfaktoren. Der Beweis dieses Satzes geht vom sogenannten „Anfänger-Traum“ (Freshmans Dream) aus:

(b +c)p = bp+ cp, b,c∈ Fpn

(3.13)

und berücksichtigt dann, daß im Grundkörper $Fp$ jedes Element $a$ die Relation $ap = a$ erfüllt (vgl. Abschnitt 3.3.2).

( ) n n n ( ) n p m (αp)= ∑ aiαip = ∑ api αip = ∑ aiαi p = ∑ aiαi = [m (α)]p = 0 i=0 i=0 i=0 i=0

Aus diesem Grund läßt sich für jedes der irreduziblen Polynome $m (x)$ die folgende Linearfaktordarstellung angeben:³⁴

n−1( i) m (x) = ∏ x− αp . i=0

Die Nullstellen $i αp$ kann man (wegen ihrer linearen Unabhängigkeit) verwenden, um statt einer Polynombasis eine so genannte Normalbasis des Vektorraumes (der Dimension $n$ ) über $Fp$ zu definieren.

Ergänzungen zu Formel 3.13

Sie kommt zustande wenn man bei der formalen Anwendung des Binomischen Satzes berücksichtigt, daß im Binomialkoeffizient $() p = --p!-- k k!(p−k)!$ der Faktor $p!$ für $k ⁄= 0$ immer durch $p$ teilbar ist und folglich $(p) k mod p = 0$ gilt. $p (p ) p−1(p ) (b+ c)p = ∑ bp−kck = bp+ cp+ ∑ bp−kck k=0 k k◟=1--k◝◜-----◞ =0$
Wendet man sie mehrfach an, dann ergibt:

$i i i (b+ c)p = bp + cp, b,c ∈Fpn.$ (3.14)

3.4.5 Erweiterungskörper $n ℤ2$

Für eine Erweiterung des Primkörpers $ℤ 2$ auf $n$ Dimensionen ist ein irreduzibles Polynom $m(x)$ vom Grad $n$ notwendig. Der dadurch entstehende Körper $n ℤ 2$ soll am Beispiel des Polynoms $2 m (x) = x + x+ 1$ mit Koeffizienten aus $ℤ2$ (zu den Rechenoperationen vgl. Seite 58) jetzt kurz betrachtet werden. Nach Darstellung 3.10 gehören genau $q = pn = 4$ Polynome zum Erweiterungskörper ( $p = 2$ , $n= 2$ ), nämlich:

Wie sich leicht feststellen läßt, ist $r3(x)$ das erzeugende Element der multiplikativen Gruppe ${r1(x),r2(x),r3(x)}$ , denn die anderen Elemente ergeben sich als Potenzen $rν(x) mod m (x) 3$ .

Außerdem sind alle Elemente (abgesehen von $r0(x)$ ) wirklich Nullstellen des Polynoms $xq−1− 1 = x3− 1= (x− 1)m (x)$ . Auch gut erkennen läßt sich, daß $m (x)$ für jedes Element $r(x)$ ein Teiler von $[r(x)]q−1− 1$ ist.

Äquivalent dazu ist das Produkt aller Elemente (konform zu Formel 2.15) genau das neutrale Element $e(⋅)$ der multiplikativen Gruppe.³⁵

2 2 r1(x)⋅r2(x)⋅r3(x)= 1 ⋅x ⋅(x +1 )= x + x≡ 1 (mod x + x+ 1)