Ein Körper (engl.: field) ist grob gesagt eine Menge von Elementen, mit denen Sie in gewohnter Weise rechnen können – wie mit den reellen Zahlen. Sie können also Elemente des Körpers addieren, subtrahieren, multiplizieren und dividieren (außer durch 0).
Dies ist gewährleistet, wenn die im Folgenden angegebenen Körperaxiome gelten.
Definition: Sei K eine Menge mit den Verknüpfungen + (Addition) und · (Multiplikation). Eine Verknüpfung ist eine Abbildung K × K → K.
Die Axiome 1-4 besagen, dass (K, +, 0), also die Menge K mit der Verknüpfung + und neutralem Element 0, eine abelsche (d.h. kommutative) Gruppe darstellt.
Die Axiome 5-8 besagen, dass (K \ {0}, ·, 1), also die Menge K \ {0} mit der Verknüpfung · und neutralem Element 1, eine abelsche Gruppe darstellt.
Die beiden Verknüpfungen + und · hängen über das Distributivgesetz (Axiom 9) zusammen.
Wenn die Menge K eine endliche Menge ist, so ist K ein endlicher Körper. Die einzigen endlichen Körper bestehen jeweils aus pm Elementen, mit p Primzahl und m ∈ ℕ.
Der einfachste endliche Körper ist die Menge ℤ2 = {0, 1} mit den Verknüpfungen +2 (Addition modulo 2) und ·2 (Multiplikation modulo 2).
Satz: Wenn p eine Primzahl ist, so ist die Menge ℤp = {0, ..., p-1} mit den Verknüpfungen +p (Addition modulo p) und ·p (Multiplikation modulo p) ein Körper. Die 0 ist das neutrale Element der Addition, die 1 ist das neutrale Element der Multiplikation.
Bemerkung: Statt ℤp ist auch die Bezeichnung 𝔽p üblich, die auf die Struktur des Körpers (field) hinweist.
Aufgabe 1:
Sei p = 7. Bestimmen Sie im Körper 𝔽7 für jedes Element jeweils das additiv inverse sowie das multiplikativ inverse Element:
| a | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| -a | 5 | ||||||
| a-1 | – | 4 |
Das additiv inverse Element beispielsweise zu 2 ist 5, denn 2 +7 5 = 0, und das multiplikativ inverse Element zu 2 ist 4, denn 2 ·7 4 = 1.
Satz: Jeder endliche Körper mit p Elementen (p Primzahl) ist zu dem Körper 𝔽p isomorph.
Sie haben einen Körper mit den Elementen {a, b, c, d, e, f, g} konstruiert, indem Sie Verknüpfungen + und · zwischen diesen Elementen definiert haben, die die Körperaxiome erfüllen. Dann erhalten Sie durch geeignete Umbenennung der Elemente a, b, c, d, e, f, g in die Zahlen 0, 1, 2, 3, 4, 5, 6 den Körper 𝔽7.
Es gibt auch Körper 𝔽n, wobei n keine Primzahl ist. Dann aber ist n eine Primzahlpotenz n = pm.
Sie erhalten einen Erweiterungskörper über einem endlichen Grundkörper K als Menge L aller Polynome vom Grad < m mit Koeffizienten aus K:
L = { am-1·xm-1 + ... + a0·x0 | m ∈ ℕ, ai ∈ K }
Sie sehen sofort, dass eine auf diese Weise konstruierte Menge L genau pm Elemente enthält, wenn p die Anzahl der Elemente des Grundkörpers K ist, denn Sie haben für jeden der m Koeffizienten jeweils p Wahlmöglichkeiten.
Beispiel: Es ist K = ℤ5 = {0, ..., 4}, ferner m = 2. Dann besteht L aus der Menge aller Polynome vom Grad < 2 mit Koeffizienten aus K:
L = { a1·x + a0 | ai ∈ K }
So sind etwa die Polynome f = 3x + 4 und g = 4x + 2 Elemente von L.
Wie aber sind die Addition und die Multiplikation auf der Menge L definiert?
Die Addition von zwei Polynomen aus L entspricht der gewohnten Polynom-Addition, also der koeffizientenweisen Addition, jedoch modulo p, wenn ℤp der zugrundeliegende Körper K ist.
Definition: (Addition + in L)
Die Addition + im Erweiterungskörper L aller Polynome vom Grad < m über dem Körper ℤp ist folgendermaßen definiert.
am-1·xm-1 + ... + a0·x0 + bm-1·xm-1 + ... + b0·x0 = (am-1 +p bm-1)·xm-1 + ... + (a0 +p b0)·x0
Mit den Koeffizienten rechnen Sie modulo p, wenn ℤp der zugrundeliegende Körper des Erweiterungskörpers L ist.
Beispiel:
Im Beispiel addieren Sie die Polynome f = 3x + 4 und g = 4x + 2 wie folgt. Weil der Körper K = ℤ5 zugrundeliegt, addieren Sie die Koeffizienten modulo 5:
f + g = 3x + 4 + 4x + 2 = (3+4)x + 4+2 = 2x + 1
Die Multiplikation • von zwei Polynomen aus L entspricht zunächst der gewohnten Polynom-Multiplikation. Dabei kann als Ergebnis jedoch ein Polynom vom Grad ≥ m herauskommen, also ein Polynom, das nicht in der Menge L liegt. Deshalb wird das Ergebnis noch modulo eines bestimmten Polynoms z vom Grad m reduziert.
Beispiel: Um die Polynome f und g aus dem Beispiel zu multiplizieren, führen Sie zunächst die gewohnte Polynom-Multiplikation aus:
(3x + 4) · (4x + 2) = 12x2 + 6x + 16x + 8
Mit den Koeffizienten rechnen Sie modulo 5 und erhalten das Ergebnis
2x2 + 2x + 3
Dieses Ergebnis reduzieren Sie noch modulo des festgelegten Polynoms z = x2 + 3:
(2x2 + 2x + 3) mod (x2 + 3) = 2x2 + 2x + 3 – 2·(x2 + 3) = 2x + 2
Damit haben Sie wieder ein Polynom erhalten, das in L liegt.
Definition: (Multiplikation • in L)
Die Multiplikation • im Erweiterungskörper L aller Polynome vom Grad < m über dem Körper ℤp ist folgendermaßen definiert.
f • g = f · g mod z
Hierbei ist z ein festgelegtes irreduzibles Polynom vom Grad m. Mit den Koeffizienten rechnen Sie modulo p, wenn ℤp der zugrundeliegende Körper des Erweiterungskörpers L ist.
Es stellt sich heraus, dass die Menge L aller Polynome vom Grad < m mit der so festgelegten Addition und Multiplikation einen Körper (L, +, • , 0, 1) darstellt.
Der Grundkörper K ist ein Teilkörper dieses Erweiterungskörpers L, bestehend aus allen Polynomen vom Grad < 1.
Je nachdem, welches irreduzible Polynom z Sie bei der Multiplikation verwenden, erhalten Sie natürlich unterschiedliche Multiplikationstabellen und damit unterschiedliche Körper. Tatsächlich aber sind diese Körper alle isomorph zueinander.
Satz: Jeder endliche Körper besteht aus pm Elementen mit p Primzahl und m ∈ ℕ, und zu jedem p und jedem m lässt sich in der dargestellten Weise ein endlicher Körper konstruieren, und tatsächlich ist dieser bis auf Isomorphie der einzige Körper mit pm Elementen.
Ein endlicher Körper mit n Elementen wird mit 𝔽n bezeichnet, oder auch mit GF(n). Hierbei bedeutet GF Galois Field (nach E. Galois).
Elliptische Kurven in der Kryptografie werden über einem Körper ℤp mit p Primzahl gebildet.
Beim AES-Verschlüsselungsverfahren wird der Körper 𝔽28 zugrundegelegt.
Weiter mit: [up]