Endlicher Körper
Definition
In der Algebra ist ein endlicher Körper oder Galoisfeld (benannt nach dem Mathematiker Evariste Galois) ein Körper mit nur endlich vielen Elementen. Endliche Körper spielen eine wichtige Rolle in der Kryptographie und der Kodierungstheorie.
Darstellung
Da jeder Körper der Charakteristik 0 unendlich ist, haben alle endlichen Körper eine Primzahlcharakteristik.
Ist p eine Primzahl, dann bildet der Restklassenring Z/pZ einen Körper, der mit Fp oder GF(p) bezeichnet wird. Jeder andere Körper mit genau p Elementen ist isomorph zu diesem.
Ist q = pn eine Primzahlpotenz, dann gibt es bis auf Isomorphie genau einen Körper mit genau q Elementen. Er wird mit Fq oder GF(q) = GF(pn) bezeichnet. Man kann ihn so konstruieren: Finde ein irreduzibles Polynom f vom Grad n mit Koeffizienten in GF(p), und setze GF(q) := GF(p)[T]/(f). GF(p)[T] bezeichnet dabei den Polynomring in der Variablen T über dem Körper GF(p), und GF(q) ist sein Faktorring modulo f. Das Polynom f kann man finden, indem man das Polynom Tq-T über GF(p) faktorisiert.
Ist K irgendein endlicher Körper der Charakteristik p, dann enthält er GF(p) als Teilkörper und ist ein Vektorraum über diesem Körper. Deshalb hat K als Mächtigkeit eine Potenz von p. Es gibt also außer den genannten keine anderen endlichen Körper.
Beispiele
Der Restklassenring der ganzen Zahlen modulo 2 ist ein als GF(2) bezeichneter Körper mit genau 2 Elementen, die als 0 und 1 bezeichnet werden. Man darf die beiden Elemente nicht verwechseln mit den ganzen Zahlen 0 und 1, denn in diesem Körper gilt 1+1=0.
Das Polynom f = T2+T+1 ist irreduzibel über GF(2). Der Körper GF(4) = GF(2)[T]/(f) kann daher als die Menge {0, 1, t, t+1} beschrieben werden mit Rechenregeln, die sich aus 1+1=0 und t2+t+1=0 ergeben. Zum Beispiel ist t*t = -t-1 = t+1. Es ist t3 = t*(t+1) = t2+t = 2t+1 = 1. Es ist also 1/t = t+1, denn eben haben wir t*(t+1) = 1 ausgerechnet.
Man beachte, dass der Körper GF(4) nichts mit dem Restklassenring Z/4Z zu tun hat, in dem z.B. 1+1 ungleich 0 ist.
Der nächstgrößere Oberkörper von GF(2) ist GF(8), der z.B. vom Polynom T3+T+1 erzeugt wird, also GF(8)=GF(2)[T]/(T3+T+1). Seine Elemente sind {0, 1, t, t+1, t2, t2+1, t2+t, t2+t+1} mit t3 = t+1. Dieser Körper ist kein Oberkörper von GF(4), weil er keine Potenz von 4 als Mächtigkeit hat.
Die ersten Oberkörper von GF(3) = Z/3Z können so dargestellt werden: GF(9) = GF(3)[T]/(T2+1), GF(27) = GF(3)[T]/(T3+2T+1).
Eigenschaften
Ist K ein endlicher Körper mit q = pn Elementen (und p prim), dann ist xq = x für alle Elemente x von K. Der Frobenius-Homorphismus f: K -> K, f(x) = xp ist bijektiv, also ein Automorphismus. Dieser Automorphismus hat die Ordnung n und erzeugt die Automorphismengruppe von K, die deshalb zyklisch ist.
Der Körper GF(pm) enthält GF(pn) genau dann, wenn n ein Teiler von m ist, denn es gibt irreduzible Polynome von jedem Grad über GF(pn).
Die multiplikative Gruppe eines endlichen Körpers ist zyklisch (wie jede endliche multiplikative Untergruppe eines Körpers). Ist also K ein Körper mit q Elementen, dann gibt es ein Element x von K, so dass K = {0, 1, x, x2, ..., xq-2}. Dieses Element x ist dabei nicht eindeudig festgelegt.
Anwendungen
Wenn wir einen Erzeuger x der multiplikativen Gruppe von K=GF(pk) festhalten, dann gibt es für jedes a ungleich 0 aus K eine eindeutig bestimmte Zahl n aus {0, 1, ... q-2} mit a = xn. Die Zahl n heißt diskreter Logarithmus von a zur Basis x. Obwohl man xn für jedes n relativ leicht berechnen kann, ist die Aufgabe, zu gegebenem a den diskreten Logarithmus n zu finden, nach dem gegenwärtigen Wissensstand für große Zahlen p und k ein extrem rechenaufwendiger Vorgang. Deshalb findet der diskrete Logarithmus Anwendung in der Kryptographie.
Endliche Körper werden auch in der Kodierungstheorie benutzt: Viele Kodes sind Teilräume von endlichdimensionalen Vektorräumen über endlichen Körpern.
Mit endliche Körpern kann man Koordinatensysteme für endliche Geometrien erzeugen, ähnlich wie die reellen Zahlen Koordinatensysteme der euklidischen Geometrie liefern.