Endlicher Körper
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 Codierungstheorie (Vorwärtsfehlerkorrektur, zum Beispiel Reed-Solomon-Codes).
Table of contents |
2 Beispiele 3 Eigenschaften 4 Anwendungen |
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.Katalog
Addition:
| Multiplikation:
|
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 t2 = 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, und der den Nullteiler 2 enthält (2*2=0 modulo 4).
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 aber kein Oberkörper von GF(4), weil seine Mächtigkeit keine Potenz von 4 ist.
Addition:
| Multiplikation:
|
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.
Ist nämlich L=GF(pm) ein Oberkörper von K=GF(pn), dann ist L auch ein Vektorraum über K, deshalb muss pm eine Potenz von pn sein, und darum ist m ein Vielfaches von n. Ist umgekehrt n ein Teiler von m, dann gibt es ein irreduzibles Polynom f vom Grad m/n über K, und der Körper K[T]/(f) stimmt mit L überein, also ist K ein Teilkörper von L.
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 in K\\{0}, so dass K\\{0} = {1, x, x2, ..., xq-2}. Dieses Element x (ein so genannter Erzeuger der multiplikativen Gruppe K\\{0}) ist dabei nicht eindeutig festgelegt.
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 Codierungstheorie benutzt: Viele Codes sind Teilräume von endlichdimensionalen Vektorräumen über endlichen Körpern.
Anwendungen