Endlicher Körper

aus Wikipedia, der freien Enzyklopädie

In der Algebra ist ein endlicher Körper oder Galoiskörper (benannt nach dem Mathematiker Évariste 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-Code).

[Bearbeiten] Katalog

Zu jedem Körper $K$ gibt es einen eindeutig bestimmten unitären Ringhomomorphismus

$\begin{matrix}\mathbb Z\to K,\quad n&\mapsto&\underbrace{1_K+\ldots+1_K}&\mathrm{f\ddot ur}\ n\in\mathbb N.\\&&n\ \mathrm{Summanden}\end{matrix}$

Ist $K$ endlich, so kann die Abbildung nicht injektiv sein, somit gibt es eine kleinste positive ganze Zahl im Kern, d. h. eine Zahl $p$ , so dass in $K$

$p=1+1+\ldots+1=0$

gilt. Man kann zeigen, dass $p$ eine Primzahl sein muss. Man nennt sie die Charakteristik von $K$ .

Für jede Primzahl $p$ ist der Restklassenring $\mathbb Z/p\mathbb Z$ ein Körper der Charakteristik $p$ und wird mit dem Symbol $\mathbb F_p$ bezeichnet. Die alternative Schreibweise $GF(p)$ (vom englischen Galois field) ist veraltet und findet nur noch in Programmiersprachen Anwendung.

Jeder endliche Körper der Charakteristik $p$ enthält $\Bbb F_p$ (bzw. eine isomorphe Kopie desselben) als Unterkörper. Er ist damit insbesondere ein Vektorraum über $\mathbb F_p$ und als solcher isomorph zu $\mathbb F_p^n$ für eine natürliche Zahl $n$ . Damit enthält er genau $p n$ Elemente. Man kann zeigen, dass es bis auf Isomorphie genau einen Körper mit $q = p n$ Elementen gibt; dieser wird dann mit $\Bbb F_q=\Bbb F_{p^n}$ bezeichnet (veraltete Alternativschreibweise $GF(p n)$ ).

$\mathbb F_q$ ist stets eine einfache Erweiterung von $\mathbb F_p$ , d. h. es gibt ein irreduzibles Polynom $f\in\mathbb F_p[X]$ vom Grad $n$ , so dass $\mathbb F_q\cong\mathbb F_p[X]/(f)$ ist. Derartig irreduzible Polynome sind stets Faktoren von $X q - X$ , vergleiche Adjunktion (Algebra).

[Bearbeiten] Beispiele

[Bearbeiten] Charakteristik 2

Im Restklassenkörper $\mathbb F_2=\{0,1\}$ der ganzen Zahlen modulo 2 gilt $1 + 1 = 0$ . Die Verknüpfungstabellen sehen so aus:

Addition:

+	0	1
0	0	1
1	1	0

Multiplikation:

*	0	1
0	0	0
1	0	1

Das Polynom $f = T 2 + T + 1$ ist irreduzibel über $\mathbb F_2$ . Der Körper $\mathbb F_4\cong\mathbb F_2[T]/(f)$ kann als die Menge ${0,1, t, t + 1}$ beschrieben werden (dabei ist $t$ eine Nullstelle von f in $\mathbb F_4$ ). Die Rechenregeln ergeben sich aus $1 + 1 = 0$ und $t 2 + t + 1 = 0$ , beispielsweise

$t\cdot t = t^2 = -(t+1) = t+1$
$t^3 = t\cdot t^2 = t(t+1) = t^2+t = -1 = 1.$
Aus $t (t + 1) = 1$ folgt auch $t - 1 = t + 1.$

Man beachte, dass der Körper $\mathbb F_4$ nichts mit dem Restklassenring $\mathbb Z/4\mathbb Z$ zu tun hat, in dem z. B. $1+1\neq0$ ist und der den Nullteiler 2 enthält ( $2\cdot 2\equiv 0\;\mathrm{mod}\,4$ ).

Der nächstgrößere Oberkörper von $\mathbb F_2$ ist $\mathbb F_8$ , der z. B. vom Polynom $T 3 + T + 1$ erzeugt wird, also $\mathbb F_8\cong\mathbb F_2[T]/(T^3+T+1).$

Seine Elemente sind

{0,1, t, t + 1, t 2, t 2 + 1, t 2 + t, t 2 + t + 1}

mit $t 3 = t + 1.$ Dieser Körper ist aber kein Oberkörper von $\mathbb F_4$ , weil seine Elementanzahl keine Potenz von 4 ist.

[Bearbeiten] Charakteristik 3

Der Restklassenkörper modulo 3

$\mathbb F_3=\mathbb Z/3\mathbb Z= \{0, 1, 2\}$

hat diese Verknüpfungstabellen:

Addition:

+	0	1	2
0	0	1	2
1	1	2	0
2	2	0	1

Multiplikation:

*	1	2
0	0	0
1	1	2
2	2	1

Die ersten Oberkörper von $\mathbb F_3$ können so dargestellt werden:

$\mathbb F_9\cong\mathbb F_3[T]/(T^2+1)$

$\mathbb F_{27}\cong\mathbb F_3[T]/(T^3-T+1)$

[Bearbeiten] Gegenbeispiel

Die Wahl p = 4 ergäbe folgenden Ring:

Addition:

+	0	1	2	3
0	0	1	2	3
1	1	2	3	0
2	2	3	0	1
3	3	0	1	2

Multiplikation:

*	1	2	3
0	0	0	0
1	1	2	3
2	2	0	2
3	3	2	1

Dabei handelt es sich aber nicht um einen Körper. In der Spalte & Zeile für die Zeile „2“ kommt in der Multiplikation nirgendwo das neutrale Element vor, folglich hat „2“ kein inverses Element. Das liegt daran, dass in diesem Falle „2“ ein Primfaktor von p = 4 ist. Ein solches Element kommt notwendigerweise für jedes p element N / Primzahlen vor.

[Bearbeiten] Mulitplikative Gruppe

Die multiplikative Gruppe $\mathbb{F}_q^*$ des endlichen Körpers $\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 $q - 1$ Elementen. Da deshalb für alle Elemente $x$ dieser Gruppe $x q - 1 = 1$ gilt, ist jedes Element eine $(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 $\varphi(q-1)$ verschiedenen Nullstellen des $(q - 1)$ -ten Kreisteilungspolynoms. ( $\varphi$ bezeichnet die Eulersche φ-Funktion.)

[Bearbeiten] Eigenschaften

Sei $p$ eine Primzahl und $q = p n$ mit $n\in\mathbb{N}$ .

Aus $x q - 1 = 1$ für alle $x\in\mathbb F_q^*$ folgt:

x q = x

für alle $x\in\mathbb F_q.$

Zu jedem Teiler k von m gibt es genau einen Zwischenkörper von , der isomorph zu ist. Man könnte auch sagen, dass der Verband der Zwischenkörper von isomorph zum Teilerverband von m ist.
- Ist nämlich $K$ ein Teilkörper von $\mathbb{F}_{q^m}$ , so ist $K$ ein $\mathbb F_q$ -Vektorraum, also ist die Anzahl der Elemente von $K$ eine Potenz von $q$ . Andererseits ist $\mathbb{F}_{q^m}$ ein Vektorraum über $K$ , und es folgt $| K | = q k$ mit $k$ teilt $m$ . $K$ ist also isomorph zu $\mathbb{F}_{q^k}$ .
- Ist umgekehrt $k$ ein Teiler von $m$ , so ist das Polynom $f(X)=X^{q^k}-X$ Teiler des Polynoms $X^{q^m}-X$ , dessen Nullstellen alle verschieden sind. Deshalb hat $f (X)$ genau $q k$ verschiedene Nullstellen in $\mathbb F_{q^m},$ und die Menge der Nullstellen bildet einen Zwischenkörper von $\mathbb F_{q^m}|\mathbb F_q,$ der isomorph zu $\mathbb F_{q^k}$ ist.
Die Abbildung $F_q\colon \mathbb{F}_{q^m}\to \mathbb{F}_{q^m}, x\mapsto x^q$ ist ein bijektiver Körperhomomorphismus, sie wird Frobenius-Automorphismus oder einfach Frobenius genannt. Der Fixkörper von $F q$ ist isomorph zu $\mathbb{F}_q$ . Die $m$ -fache Verkettung $F_q^m$ ist die Identität auf $\mathbb F_{q^m}.$
Da jede endliche Erweiterung von $\mathbb F_q$ höchstens einen Körper enthält, der isomorph zu $\mathbb F_{q^m}$ ist, sind Erweiterungen endlicher Körper stets normal.
$\mathbb F_{q^m}$ ist der Zerfällungskörper des separablen Polynoms $X^{q^m}-X$ über $\mathbb F_q$ , also sind Erweiterungen endlicher Körper auch stets separabel; endliche Körper sind also vollkommen.
Die Galoisgruppe $\mbox{Gal}(\mathbb{F}_{q^m}/\mathbb{F}_q)$ ist zyklisch und hat die Ordnung $m$ . Sie hat einen kanonischen Erzeuger, den Frobenius-Automorphismus $F q$ .
Kein endlicher Körper ist algebraisch abgeschlossen: Das Polynom $1 + \prod_{a \in \mathbb{F}_q} (X-a)=X^q-X+1$ hat keine Nullstelle im Körper $\mathbb{F}_q$ .

[Bearbeiten] Anwendungen

Wenn wir einen Erzeuger x der multiplikativen Gruppe von $\Bbb F_q$ mit $q = p n$ festhalten, dann gibt es für jedes a ungleich 0 aus K eine eindeutig bestimmte Zahl m aus {0, 1, … q-2} mit a = x^m. Die Zahl m heißt diskreter Logarithmus von a zur Basis x. Obwohl man x^m für jedes m relativ leicht berechnen kann, ist die Aufgabe, zu gegebenem a den diskreten Logarithmus m zu finden, nach dem gegenwärtigen Wissensstand für große Zahlen p und n 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.

[Bearbeiten] Literatur

A. Steger: Diskrete Strukturen 1 Springer-Verlag, Berlin, Heidelberg, New York, ISBN 978-3-540-46660-4, Seite 223ff.

Kategorie: Algebra

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Endlicher Körper

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis

[Bearbeiten] Katalog

[Bearbeiten] Beispiele

[Bearbeiten] Charakteristik 2

[Bearbeiten] Charakteristik 3

[Bearbeiten] Gegenbeispiel

[Bearbeiten] Mulitplikative Gruppe

[Bearbeiten] Eigenschaften

[Bearbeiten] Anwendungen

[Bearbeiten] Literatur

Views

Navigation

Mitmachen

Suche

Andere Sprachen