Endlicher Körper

In d​er Algebra, e​inem Teilgebiet d​er Mathematik, i​st ein endlicher Körper o​der Galoiskörper (nach Évariste Galois) e​in Körper m​it einer endlichen Anzahl v​on Elementen, d. h. e​ine endliche Menge, a​uf der z​wei als Addition u​nd Multiplikation verstandene Grundoperationen definiert sind, sodass d​ie Menge zusammen m​it diesen Operationen a​lle Anforderungen e​ines Körpers erfüllt.

Endliche Körper spielen eine wichtige Rolle in der Kryptographie und der Codierungstheorie (Vorwärtsfehlerkorrektur, zum Beispiel beim Reed-Solomon-Code). Daneben sind sie grundlegend für das Studium der Primideale im Ring der ganzen Zahlen einer endlichen Körpererweiterung von ${\displaystyle \mathbb {Q} }$ im Rahmen der algebraischen Zahlentheorie. Man vergleiche hierzu auch Verzweigung im Kontext von Erweiterungen von Dedekindringen.

Außerdem s​ind endliche Körper i​n der Geometrie a​ls Koordinatenbereiche endlicher Geometrien v​on Bedeutung. Sie s​ind allgemeiner Koordinatenbereiche v​on Ebenen u​nd Räumen i​n der synthetischen Geometrie. Mit Hilfe d​er Addition u​nd Multiplikation i​n einem endlichen Körper werden h​ier Verknüpfungen m​it schwächeren algebraischen Eigenschaften definiert, d​ie aus d​em Körper z. B. e​inen Ternär- o​der Quasikörper machen. Auf diesen verallgemeinerten Körpern können d​ann projektive u​nd affine Ebenen konstruiert werden.

Die Anzahl der Elemente eines endlichen Körpers ist immer eine Primzahlpotenz. Für jede Primzahl ${\displaystyle p}$ und jede positive natürliche Zahl ${\displaystyle n}$ existiert (bis auf Isomorphie) genau ein Körper mit ${\displaystyle p^{n}}$ Elementen, der mit ${\displaystyle \mathbb {F} _{p^{n}}}$ oder ${\displaystyle \operatorname {GF} (p^{n})}$ bezeichnet wird. ${\displaystyle \mathbb {F} _{p}=\operatorname {GF} (p)}$ ist der Körper der Restklassen ganzer Zahlen modulo ${\displaystyle p}$.

E. H. Moore prägte wohl 1893 den englischen Begriff Galois field zu Ehren von Évariste Galois, der bereits mit gewissen imaginären Zahlen modulo ${\displaystyle p}$ gerechnet hat.

Der Satz v​on Wedderburn s​agt aus, d​ass die Multiplikation i​n einem endlichen Schiefkörper notwendig kommutativ ist. Das heißt, d​ass endliche Schiefkörper s​tets endliche Körper sind.

Beispiel: Der Körper mit 2 Elementen

Die Restklassen modulo 2 bilden den Körper ${\displaystyle \mathbb {F} _{2}=\operatorname {GF} (2)}$ mit zwei Elementen. ${\textstyle 0}$ repräsentiere die Restklasse ${\displaystyle 2\mathbb {Z} }$ der geraden Zahlen, ${\displaystyle 1}$ die Restklasse ${\displaystyle 1+2\mathbb {Z} }$ der ungeraden Zahlen. Für die Addition gilt:

${\displaystyle 0+0=0,\qquad 0+1=1,\qquad 1+0=1,\qquad 1+1=0}$

Für d​ie Multiplikation gilt:

${\displaystyle 0\cdot 0=0\cdot 1=1\cdot 0=0}$ und ${\displaystyle 1\cdot 1=1}$

Klassifikation endlicher Körper

Ist ${\displaystyle \mathbb {K} }$ ein endlicher Körper, so ist der Kern des Ringhomomorphismus ${\displaystyle f\colon \mathbb {Z} \to \mathbb {K} }$, ${\displaystyle n\mapsto n\cdot 1}$ stets von der Form ${\displaystyle p\mathbb {Z} }$ mit einer gewissen Primzahl ${\displaystyle p}$, d. h., er besteht aus allen Vielfachen von ${\displaystyle p}$. Dabei beachte man, dass 1 keine Primzahl ist. Diese Primzahl ${\displaystyle p}$ heißt die Charakteristik von ${\displaystyle \mathbb {K} }$. Das Bild von ${\displaystyle f}$ ist nach dem Homomorphiesatz für Ringe isomorph zum Restklassenkörper ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ und heißt der Primkörper von ${\displaystyle \mathbb {K} }$. Als endlicher Erweiterungskörper ist ${\displaystyle \mathbb {K} }$ zugleich ein ${\displaystyle n}$-dimensionaler Vektorraum über seinem Primkörper. Somit hat ${\displaystyle \mathbb {K} }$ genau ${\displaystyle q=p^{n}}$ Elemente.

In einem Körper ${\displaystyle \mathbb {K} }$ mit Charakteristik ${\displaystyle p>0}$ ist die Abbildung

${\displaystyle {\mathcal {F}}\colon \mathbb {K} \to \mathbb {K} :x\mapsto x^{p}}$

wegen

${\displaystyle (x+y)^{p}=x^{p}+y^{p}}$

ein Homomorphismus additiver Gruppen.

Die übrigen nach der binomischen Formel auf der rechten Seite auftretenden Summanden fallen wegen ${\displaystyle {\tbinom {p}{i}}\equiv 0{\pmod {p}}}$ für ${\displaystyle 1\leq i<p}$ fort. ${\displaystyle {\mathcal {F}}}$ trägt zu Ehren Ferdinand Georg Frobenius’ den Namen Frobeniushomomorphismus, der ein Automorphismus ist und deshalb auch Frobeniusautomorphismus genannt wird. Der Primkörper wird durch ${\displaystyle {\mathcal {F}}}$ punktweise fixiert (in der Tat ist z. B. ${\displaystyle 4^{7}-4}$ ein Vielfaches von 7). Ebenso ist ${\displaystyle {\mathcal {F}}^{n}=\mathrm {id} }$ auf jedem Körper mit ${\displaystyle q=p^{n}}$ Elementen. Andererseits besitzt ${\displaystyle x^{p^{n}}-x}$ als Polynom vom Grad ${\displaystyle p^{n}}$ höchstens ${\displaystyle p^{n}}$ verschiedene Nullstellen. Diese sind alle durch die Elemente von ${\displaystyle \mathbb {K} }$ erfasst.

Hieraus lässt s​ich folgern:

• Für jede Primzahl ${\displaystyle p}$ und jede natürliche Zahl ${\displaystyle n}$ gibt bis auf Isomorphie genau einen Körper ${\displaystyle \mathbb {F} _{q}}$ mit ${\displaystyle q=p^{n}}$ Elementen.
• Dieser stellt eine Galois-Erweiterung seines Primkörpers dar.
• Die Galoisgruppe ist zyklisch von Ordnung ${\displaystyle n}$ und wird von ${\displaystyle {\mathcal {F}}}$ erzeugt.

Weitere Eigenschaften endlicher Körper:

• Alle Elemente außer 0 der additiven Gruppe eines endlichen Körpers der Charakteristik ${\displaystyle p}$ haben Ordnung ${\displaystyle p.}$
• Wie bei jeder endlichen separablen Körpererweiterung gibt es stets ein primitives Element, also ein ${\displaystyle x\in \mathbb {F} _{q}}$ derart, dass der Erweiterungskörper durch Adjunktion nur dieses einen Elements entsteht. Ist ${\displaystyle f\in \mathbb {F} _{p}[X]}$ das Minimalpolynom von ${\displaystyle x,}$ so hat ${\displaystyle f}$ den Grad ${\displaystyle n}$ und es gilt ${\displaystyle \mathbb {F} _{q}\cong \mathbb {F} _{p}[X]/(f)}$. Ferner ist ${\displaystyle \mathbb {F} _{q}}$ stets bereits der Zerfällungskörper von ${\displaystyle f}$, d. h., ${\displaystyle f}$ zerfällt über ${\displaystyle \mathbb {F} _{q}}$ vollständig in Linearfaktoren.
• Ist ${\displaystyle m}$ ein Teiler von ${\displaystyle n}$, so ist ${\displaystyle \mathbb {F} _{p^{m}}\subset \mathbb {F} _{p^{n}}}$ eine Galois-Erweiterung vom Grad ${\displaystyle n/m}$. Die zugehörige Galois-Gruppe ist ebenfalls zyklisch und wird von der ${\displaystyle m}$-ten Potenz ${\displaystyle {\mathcal {F}}^{m}}$ des Frobeniusautomorphismus erzeugt.

Multiplikative Gruppe und diskreter Logarithmus

Die multiplikative Gruppe ${\displaystyle \mathbb {F} _{q}^{*}}$ (${\displaystyle \mathbb {F} _{q}^{\times }}$) des endlichen Körpers ${\displaystyle \mathbb {F} _{q}}$ besteht aus allen Elementen des Körpers mit Ausnahme der Null. Die Gruppenoperation ist die Multiplikation des Körpers.

Die multiplikative Gruppe ist eine zyklische Gruppe mit ${\displaystyle q-1}$ Elementen. Da deshalb für alle Elemente ${\displaystyle x}$ dieser Gruppe ${\displaystyle x^{q-1}=1}$ gilt, ist jedes Element eine ${\displaystyle (q-1)}$-te Einheitswurzel des Körpers. Diejenigen Einheitswurzeln, die Erzeuger der multiplikativen Gruppe sind, werden als primitive Einheitswurzeln oder Primitivwurzeln bezeichnet. Es sind dies die ${\displaystyle \varphi (q-1)}$ verschiedenen Nullstellen des ${\displaystyle (q-1)}$-ten Kreisteilungspolynoms. (${\displaystyle \varphi }$ bezeichnet die eulersche φ-Funktion.)

Ist ${\displaystyle x}$ eine Primitivwurzel der multiplikativen Gruppe ${\displaystyle \mathbb {F} _{q}^{*}}$, dann lässt sich die multiplikative Gruppe als Menge ${\displaystyle \left\{x^{0},x^{1},x^{2},\dotsc ,x^{q-2}\right\}}$ darstellen. Ein solches ${\displaystyle x}$ wird daher auch als Erzeuger oder Generator bezeichnet. Für jedes Element ${\displaystyle a}$ gibt es eine eindeutig bestimmte Zahl ${\displaystyle m\in \{0,1,2,\dotsc ,q-2\}}$ mit ${\displaystyle a=x^{m}}$. Diese Zahl ${\displaystyle m}$ heißt diskreter Logarithmus von ${\displaystyle a}$ zur Basis ${\displaystyle x}$. Obwohl sich ${\displaystyle x^{m}}$ für jedes ${\displaystyle m}$ problemlos berechnen lässt, ist die Aufgabe, zu gegebenem ${\displaystyle a}$ den diskreten Logarithmus ${\displaystyle m}$ zu finden, nach gegenwärtigem Wissensstand für große Zahlen ${\displaystyle q}$ ein extrem rechenaufwändiger Vorgang. Deshalb findet der diskrete Logarithmus Anwendung in der Kryptographie, etwa beim Diffie-Hellman-Schlüsselaustausch.

Weitere Beispiele

Der Körper ${\displaystyle \mathbb {F} _{p^{n}}}$ kann mit Hilfe des Primkörpers ${\displaystyle \mathbb {F} _{p}\cong \mathbb {Z} /p\mathbb {Z} }$ konstruiert werden: Da ${\displaystyle \mathbb {F} _{p}[X]}$ ein Hauptidealring ist, erzeugt jedes irreduzible Element ein maximales Ideal. Für ein irreduzibles Polynom ${\displaystyle f(X)\in \mathbb {F} _{p}[X]}$ vom Grad ${\displaystyle n}$ ist der Faktorring ${\displaystyle \mathbb {F} _{p}[X]/(f(X))}$ damit ein Körper mit ${\displaystyle p^{n}}$ Elementen.

Der Körper mit 4 Elementen

Für den Fall ${\displaystyle p^{n}=2^{2}}$ wird ein irreduzibles Polynom 2-ten Grades über ${\displaystyle \mathbb {F} _{2}}$ gesucht. Es existiert nur ein einziges, nämlich ${\displaystyle f(X)=X^{2}+X+1}$. Die Elemente des Körpers ${\displaystyle \mathbb {F} _{4}}$ sind die Restklassen des Faktorrings ${\displaystyle \mathbb {F} _{2}[X]/(f(X))}$. Die ${\displaystyle X}$ enthaltende Restklasse sei mit ${\displaystyle x}$ bezeichnet, so dass ${\displaystyle x}$ Nullstelle von ${\displaystyle f(X)}$ in ${\displaystyle \mathbb {F} _{2}[X]}$ ist. Die andere Nullstelle ist dann ${\displaystyle x+1,}$ denn es ist

${\displaystyle (x+1)^{2}+(x+1)+1=x^{2}+2x+1+x+1+1=x^{2}+x+1=f(x)=0.}$

Das Produkt von ${\displaystyle x,x+1\in \mathbb {F} _{4}}$ berechnet sich beispielsweise dann als

${\displaystyle x\times (x+1)=x^{2}+x=1+x^{2}+x+1=1+f(x)=1}$.

Die vollständigen Verknüpfungstafeln für Addition (+) und Multiplikation (×) in ${\displaystyle \mathbb {F} _{4}}$ lauten:

+ 0 1 x x+1 0 0 1 x x+1 1 1 0 x+1 x x x x+1 0 1 x+1 x+1 x 1 0

× 000 1 x x+1 0 0 0 0 0 1 0 1 x x+1 x 0 x x+1 1 x+1 0 x+1 1 x

Farblich hinterlegt ist der Unterkörper ${\displaystyle \mathbb {F} _{2}}$.

Der Körper mit 49 Elementen

Im Primkörper ${\displaystyle \mathbb {F} _{7}\cong \mathbb {Z} /7\mathbb {Z} }$ ist −1 kein Quadrat. Dies folgt aus dem 1. Ergänzungssatz zum quadratischen Reziprozitätsgesetz von Carl Friedrich Gauß oder – bei einer derart kleinen Primzahl – durch explizites Quadrieren aller sechs Elemente der multiplikativen Gruppe. So wie die komplexen Zahlen ${\displaystyle \mathbb {C} }$ aus den reellen Zahlen durch Adjunktion einer Zahl ${\displaystyle \mathrm {i} }$ mit ${\displaystyle \mathrm {i} ^{2}=-1}$ entstehen, lässt sich auch ${\displaystyle \mathbb {F} _{49}}$ aus ${\displaystyle \mathbb {F} _{7}}$ durch Adjunktion einer „Zahl“ ${\displaystyle j}$ mit ${\displaystyle j^{2}=-1=6}$ gewinnen; formal korrekt als ${\displaystyle \mathbb {F} _{49}\cong \mathbb {F} _{7}[X]/(X^{2}+1).}$ Gleichzeitig ist ${\displaystyle \mathbb {F} _{49}\cong \mathbb {Z} [\,\mathrm {i} \,]/(7)}$ auch ein Faktorring des Rings der ganzen Gaußschen Zahlen.

Der Körper mit 25 Elementen

In Charakteristik 5 ist −1 stets ein Quadrat: ${\displaystyle 2^{2}\equiv -1{\pmod {5}}}$. Keine Quadrate modulo 5 sind jedoch die Zahlen 2 und 3. (In Charakteristik ${\displaystyle p}$ mit ${\displaystyle p>2}$ sind stets genau die Hälfte der Elemente der multiplikativen Gruppe ${\displaystyle \mathbb {F} _{q}^{*}}$ Quadrate bzw. Nichtquadrate.) Man kann also den Körper mit 25 Elementen als ${\displaystyle \mathbb {F} _{5}[X]/(X^{2}-2)}$, also durch Adjunktion von ${\displaystyle {\sqrt {2}}}$ erhalten.

Zur historischen Entwicklung

Dass man mit Zahlen modulo einer Primzahl „wie mit rationalen Zahlen“ rechnen kann, hatte bereits Gauß gezeigt.[1] Galois führte in die Rechnung modulo ${\displaystyle p}$ imaginäre Zahlgrößen ein, ganz so wie die imaginäre Einheit ${\displaystyle \mathrm {i} }$ in den komplexen Zahlen. Damit hat er wohl als erster Körpererweiterungen von ${\displaystyle \mathbb {F} _{p}}$ betrachtet – wenn auch der abstrakte Körperbegriff erst 1895 durch Heinrich Weber eingeführt wurde und Frobenius als Erster diesen 1896 auf endliche Strukturen ausdehnte. Daneben bzw. zuvor hat offenbar Eliakim Hastings Moore 1893 bereits endliche Körper studiert und den Namen Galois field eingeführt.[2]

Literatur

• Dieter Jungnickel: Finite fields: Structure and arithmetics. B.I. Wissenschaftsverlag, 1993, ISBN 3-411-16111-6.
• Hans Kurzweil: Endliche Körper. Verstehen, Rechnen, Anwenden. Springer, ISBN 978-3-540-795971.

Zur historischen Entwicklung:

• Hans Wußing: 6000 Jahre Mathematik. Bd. 1. Springer, Berlin 2008. ISBN 978-3-540-77189-0.

Fußnoten und Einzelnachweise

1. Zur historischen Entwicklung vgl. man Wußing, S. 354 ff.
2. Vgl. Earliest Known Uses of Some of the Words of Mathematics (F). Abgerufen am 12. September 2009.