Endlicher Körper

Grundidee und Bedeutung

Ein endlicher Körper, auch Galoiskörper genannt, ist in der Algebra ein Körper mit endlich vielen Elementen. Ein Körper ist eine Menge, in der Addition, Subtraktion, Multiplikation und Division durch jedes von 0 verschiedene Element möglich sind. Dabei gelten die bekannten Rechenregeln: Kommutativgesetz, Assoziativgesetz und Distributivgesetz. Außerdem gehören 0 als neutrales Element der Addition und 1 als neutrales Element der Multiplikation dazu.

Endliche Körper sind wichtig in der Kryptographie und in der Codierungstheorie, zum Beispiel bei der Vorwärtsfehlerkorrektur und beim Reed-Solomon-Code. Außerdem spielen sie in der algebraischen Zahlentheorie und in der Geometrie eine Rolle, etwa als Koordinatenbereiche endlicher Geometrien. Aus ihnen lassen sich auch verallgemeinerte algebraische Strukturen wie Ternärkörper oder Quasikörper gewinnen, mit denen projektive und affine Ebenen konstruiert werden können.

Die Anzahl der Elemente eines endlichen Körpers ist immer eine Primzahlpotenz. Für jede Primzahl p und jede positive natürliche Zahl n gibt es bis auf Isomorphie genau einen Körper mit p^n Elementen. Er wird mit F_{p^n} oder GF(p^n) bezeichnet. Der Körper F_p = GF(p) ist der Körper der Restklassen ganzer Zahlen modulo p. Der Satz von Wedderburn besagt außerdem, dass die Multiplikation in einem endlichen Schiefkörper notwendig kommutativ ist; endliche Schiefkörper sind also immer endliche Körper.

Rechnen modulo einer Primzahl

In einem endlichen Körper K können die Elemente 1, 1+1, 1+1+1 und so weiter nicht alle verschieden sein, weil K nur endlich viele Elemente hat. Da 0 != 1 gilt, gibt es eine kleinste natürliche Zahl p, für die 1+1+...+1 = 0 gilt, wobei 1 genau p-mal addiert wird. Diese Zahl heißt Charakteristik des Körpers, geschrieben char(K)=p. Sie ist immer eine Primzahl. Wäre sie zusammengesetzt, zum Beispiel 2·3, dann müsste bereits einer der Faktoren im Körper zu 0 führen; das würde der Minimalität der Charakteristik widersprechen.

Die einfachsten endlichen Körper entstehen durch Rechnen mit Restklassen modulo einer Primzahl. Bei Division durch 5 gibt es zum Beispiel die fünf Restklassen 0, 1, 2, 3 und 4 modulo 5. Die Restklasse 4 enthält alle ganzen Zahlen, die bei Division durch 5 den Rest 4 haben, also etwa ..., -6, -1, 4, 9, 14, 19, ... . Entscheidend ist nicht die Größe einer Zahl, sondern nur ihr Rest.

Mit diesen Restklassen kann man rechnen: 4+4 = 8 = 3 modulo 5, 4-39 = -35 = 0 modulo 5 und 2·3 = 6 = 1 modulo 5. Die Rechenoperationen sind wohldefiniert, weil die Wahl anderer Vertreter derselben Restklasse dasselbe Ergebnis liefert. Division ist ebenfalls möglich, solange nicht durch 0 dividiert wird. Der Grund ist, dass p eine Primzahl ist: Wenn p ein Produkt teilt, muss p mindestens einen Faktor teilen. Dadurch besitzt jedes von 0 verschiedene Element ein multiplikatives Inverses. Zum Beispiel ist 2 ein Inverses von 3 modulo 5, denn 2·3 = 6 = 1 modulo 5. Allgemein erhält man so zu jeder Primzahl p den endlichen Körper F_p.

Klassifikation

Für einen endlichen Körper K betrachtet man den Ringhomomorphismus f: Z -> K, n -> n·1. Sein Kern hat die Form pZ für eine Primzahl p; diese Primzahl ist die Charakteristik von K. Das Bild von f ist nach dem Homomorphiesatz für Ringe isomorph zu Z/pZ und heißt Primkörper von K. Als endlicher Erweiterungskörper ist K ein n-dimensionaler Vektorraum über seinem Primkörper. Daher hat K genau q=p^n Elemente.

In einem Körper der Charakteristik p>0 ist die Abbildung F: K -> K, x -> x^p ein Homomorphismus additiver Gruppen, weil (x+y)^p = x^p + y^p gilt. Die übrigen Summanden der binomischen Formel verschwinden, da die Binomialkoeffizienten durch p teilbar sind. Diese Abbildung heißt Frobeniushomomorphismus, nach Ferdinand Georg Frobenius. Da sie ein Automorphismus ist, nennt man sie auch Frobeniusautomorphismus. Der Primkörper wird durch sie punktweise fixiert, und auf einem Körper mit q=p^n Elementen gilt F^n = id.

Daraus folgt die zentrale Klassifikation: Für jede Primzahl p und jede natürliche Zahl n gibt es bis auf Isomorphie genau einen Körper F_q mit q=p^n Elementen. Dieser Körper ist eine Galois-Erweiterung seines Primkörpers. Seine Galoisgruppe ist zyklisch von Ordnung n und wird vom Frobeniusautomorphismus erzeugt.

Weitere wichtige Eigenschaften sind: Alle von 0 verschiedenen Elemente der additiven Gruppe eines endlichen Körpers der Charakteristik p haben Ordnung p. Außerdem gibt es stets ein primitives Element x, sodass der Erweiterungskörper durch Adjunktion dieses einen Elements entsteht. Ist f in F_p[X] das Minimalpolynom von x, dann hat f Grad n, und F_q ist isomorph zu F_p[X]/(f). Ist m ein Teiler von n, dann ist F_{p^m} in F_{p^n} enthalten; diese Erweiterung hat Grad n/m, und ihre Galoisgruppe wird von F^m erzeugt.

Multiplikative Gruppe

Die multiplikative Gruppe F_q^* oder F_q^× eines endlichen Körpers F_q besteht aus allen Körperelementen außer 0. Ihre Gruppenoperation ist die Multiplikation. Diese Gruppe ist zyklisch und hat q-1 Elemente. Daher gilt für jedes Element x dieser Gruppe: x^{q-1}=1. Jedes von 0 verschiedene Element ist also eine (q-1)-te Einheitswurzel.

Die Erzeuger der multiplikativen Gruppe heißen primitive Einheitswurzeln oder Primitivwurzeln. Es gibt davon φ(q-1), wobei φ die eulersche φ-Funktion bezeichnet. Ist x eine Primitivwurzel, dann lässt sich die multiplikative Gruppe als {x^0, x^1, x^2, ..., x^{q-2}} schreiben. Für jedes Element a der Gruppe gibt es dann genau eine Zahl m aus {0,1,2,...,q-2} mit a=x^m. Diese Zahl m heißt diskreter Logarithmus von a zur Basis x.

Das Berechnen von x^m ist leicht möglich. Umgekehrt ist es nach gegenwärtigem Wissensstand für große q extrem rechenaufwändig, zu gegebenem a den diskreten Logarithmus m zu finden. Deshalb wird der diskrete Logarithmus in der Kryptographie verwendet, zum Beispiel beim Diffie-Hellman-Schlüsselaustausch.

Typische Beispiele

Endliche Körper mit p^n Elementen kann man mithilfe des Primkörpers F_p konstruieren. Da F_p[X] ein Hauptidealring ist, erzeugt jedes irreduzible Polynom f(X) in F_p[X] ein maximales Ideal. Hat f Grad n, dann ist der Faktorring F_p[X]/(f(X)) ein Körper mit p^n Elementen.

Der Körper F_2 = GF(2) hat zwei Elemente. Dabei steht 0 für die geraden Zahlen und 1 für die ungeraden Zahlen. Für die Addition gilt 0+0=0, 0+1=1, 1+0=1 und 1+1=0. Für die Multiplikation gilt 0·0=0·1=1·0=0 und 1·1=1.

Der Körper F_4 entsteht für p^n=2^2. Dafür braucht man ein irreduzibles Polynom zweiten Grades über F_2. Es gibt nur eines: f(X)=X^2+X+1. Die Elemente von F_4 sind die Restklassen des Faktorrings F_2[X]/(f(X)). Bezeichnet man die Restklasse von X mit x, dann ist x eine Nullstelle von f. Die andere Nullstelle ist x+1. Ein Beispiel für die Multiplikation ist x·(x+1)=x^2+x=1, weil f(x)=x^2+x+1=0 gilt.

Der Körper F_49 kann aus F_7 konstruiert werden. In F_7 ist -1 kein Quadrat. Daher kann man ähnlich wie bei der Konstruktion der komplexen Zahlen eine Zahl j mit j^2=-1=6 adjungieren. Formal gilt F_49 ≅ F_7[X]/(X^2+1). Der Körper F_25 kann als F_5[X]/(X^2-2) beschrieben werden, weil in Charakteristik 5 zwar -1 ein Quadrat ist, nämlich 2^2 ≡ -1 mod 5, aber 2 und 3 keine Quadrate modulo 5 sind.