Ringe und Körper

Mit den ganzen Zahlen $\mathbb{Z}$ kannst du addieren, subtrahieren und multiplizieren, aber nicht immer dividieren: $3:2$ liegt nicht mehr in $\mathbb{Z}$. Mit den rationalen Zahlen $\mathbb{Q}$ geht auch das Dividieren. Diesen Unterschied fasst die Algebra in zwei Begriffen: Ein Ring ist eine Menge mit Addition und Multiplikation, in der man wie in $\mathbb{Z}$ rechnet. Ein Körper ist ein Ring, in dem man durch alles außer 0 teilen darf. Die Begriffe bilden den Rahmen für die lineare Algebra (Vektorräume über Körpern), die Zahlentheorie und die Kryptographie.

Hier lernst du die Axiome, wichtige Beispiele wie die Restklassen ${\mathbb{Z}}_n$ und Polynomringe, den Satz „${\mathbb{Z}}_n$ ist Körper genau für Primzahl $n$“, die Gruppe der Einheiten mit der Eulerschen $\phi$-Funktion, Ringhomomorphismen und Ideale. Die Grundlagen zu Gruppen stehen auf der Seite Gruppentheorie, die Kongruenzen auf Modulare Arithmetik. Zum Üben gibt es einen Aufgabengenerator.

Ringe

Beispiele: die ganzen Zahlen $\mathbb{Z}$, die rationalen, reellen und komplexen Zahlen, die Restklassen ${\mathbb{Z}}_n$, die Polynome $ℝ[x]$ und die $2\times 2$-Matrizen $M_2(ℝ)$. Der letzte Ring ist nicht kommutativ, denn für Matrizen gilt im Allgemeinen $AB\ne BA$. Die Matrizenmultiplikation zeigt das.

Aus den Axiomen folgen Rechenregeln, die man sonst als selbstverständlich nimmt. Zum Beispiel gilt $0·a=0$: Aus $0·a=(0+0)·a=0·a+0·a$ folgt durch Addition des Negativen $0=0·a$. Ebenso folgt $(-1)·a=-a$ und $(-a)(-b)=ab$.

Nullteiler

In $\mathbb{Z}$, $\mathbb{Q}$ und $ℝ$ gilt: Ist $ab=0$, dann ist $a=0$ oder $b=0$. In anderen Ringen stimmt das nicht. Ein Element $a\ne 0$ heißt Nullteiler, wenn es ein $b\ne 0$ mit $ab=0$ gibt. In ${\mathbb{Z}}_6$ gilt $2·3=6=0$, also sind 2 und 3 Nullteiler, ebenso 4 (denn $4·3=12=0$). Auch bei Matrizen gibt es Nullteiler: $\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right)\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right)$ ist die Nullmatrix. Ein kommutativer Ring mit $1\ne 0$ ohne Nullteiler heißt Integritätsbereich. Nur in Integritätsbereichen darf man kürzen: aus $ac=bc$ und $c\ne 0$ folgt $a=b$. In ${\mathbb{Z}}_6$ gilt $2·3=4·3$, aber $2\ne 4$.

Körper

Bekannte Körper sind $\mathbb{Q}$, $ℝ$ und $ℂ$. $\mathbb{Z}$ ist kein Körper, denn 2 hat in $\mathbb{Z}$ keinen Kehrwert. Jeder Körper ist nullteilerfrei: Ist $ab=0$ und $a\ne 0$, dann folgt $b=a^{-1}ab=0$. Es gibt aber auch endliche Körper, und sie sind für die Informatik wichtig.

Beweis. Ist $n$ prim und $0<a<n$, dann ist $\mathrm{ggT}(a,n)=1$. Der erweiterte euklidische Algorithmus liefert Zahlen $x,y$ mit $ax+ny=1$, also $ax\equiv 1(\mathrm{mod}n)$, und $x$ ist das Inverse. Ist $n=ab$ mit $1<a,b<n$, dann sind $a$ und $b$ Nullteiler ($ab\equiv 0$), also kann es kein Körper sein.

Das ist die Eigenschaft, die die Kryptographie braucht: In einem endlichen Körper kann man dividieren, ohne Rundungsfehler und mit endlich vielen Zahlen. Die zugehörigen Verfahren (Diffie-Hellman, elliptische Kurven) rechnen in ${\mathbb{Z}}_p$ mit großen Primzahlen $p$.

Einheiten und die Eulersche φ-Funktion

Ein Element $a$ eines Rings mit Eins heißt Einheit, wenn es ein $b$ mit $ab=ba=1$ gibt. Die Einheiten bilden bezüglich der Multiplikation eine Gruppe $R^{\times }$. In $\mathbb{Z}$ sind das nur $\pm 1$, in einem Körper alle Elemente außer 0. Im Restklassenring gilt:

Die Zahl der Einheiten lässt sich berechnen: $\phi (p)=p-1$ für eine Primzahl $p$, $\phi (p^k)=p^k-p^{k-1}$, und für teilerfremde $m,n$ gilt $\phi (mn)=\phi (m)\phi (n)$ (das folgt aus dem chinesischen Restsatz).

Beweis. Die Einheiten ${\mathbb{Z}}_n^{\times }$ bilden eine Gruppe der Ordnung $\phi (n)$. Nach dem Satz von Lagrange teilt die Ordnung jedes Elements die Gruppenordnung, also ist $a^{\phi (n)}=1$ in ${\mathbb{Z}}_n^{\times }$.

Der Satz ist die Grundlage des RSA-Verfahrens: Mit $n=pq$ ist $\phi (n)=(p-1)(q-1)$, und die Verschlüsselung $m\mapsto m^e$ wird durch $m\mapsto m^d$ mit $ed\equiv 1(\mathrm{mod}\phi (n))$ rückgängig gemacht. Eine Einführung steht bei Primzahlen und Verschlüsselung.

RSA und der Satz von Euler

Das RSA-Verfahren, mit dem Browser und Banken Nachrichten verschlüsseln, ist angewandte Algebra in ${\mathbb{Z}}_n$. Wie ein Schlüsselpaar entsteht und was Ver- und Entschlüsseln in Zahlen heißt, steht in der Schulfassung unter Öffentlicher Schlüssel und RSA mit dem Mini-Beispiel $n=33$. Hier kommt der Beweis, dass das Entschlüsseln wirklich die Nachricht zurückgibt.

Das Verfahren

Wähle zwei verschiedene Primzahlen $p$ und $q$ und setze $n=pq$. Nach dem chinesischen Restsatz und der Produktformel ist $\phi (n)=(p-1)(q-1)$. Wähle einen öffentlichen Exponenten $e$ mit $\mathrm{ggT}(e,\phi (n))=1$. Dann hat $e$ ein Inverses modulo $\phi (n)$, und du bestimmst den privaten Exponenten $d$ mit $e·d\equiv 1(\mathrm{mod}\phi (n))$, mit dem erweiterten euklidischen Algorithmus. Der öffentliche Schlüssel ist $(n,e)$, der private ist $d$. Eine Nachricht $m\in \{0,1,\dots ,n-1\}$ wird zu $c\equiv m^e(\mathrm{mod}n)$ verschlüsselt und mit $m\equiv c^d(\mathrm{mod}n)$ wieder entschlüsselt.

Beweis. Aus $ed\equiv 1(\mathrm{mod}\phi (n))$ folgt $ed=1+k(p-1)(q-1)$ mit einem $k\ge 0$. Wir zeigen die Kongruenz getrennt modulo $p$ und modulo $q$. Fall 1: $p\nmid m$. Nach dem kleinen Satz von Fermat ist $m^{p-1}\equiv 1(\mathrm{mod}p)$, also $m^{ed}=m·{(m^{p-1})}^{k(q-1)}\equiv m·1=m(\mathrm{mod}p)$. Fall 2: $p\mid m$. Dann sind beide Seiten $\equiv 0(\mathrm{mod}p)$. Genauso zeigt man $m^{ed}\equiv m(\mathrm{mod}q)$. Da $p$ und $q$ teilerfremd sind, folgt $m^{ed}\equiv m(\mathrm{mod}pq)$ aus dem chinesischen Restsatz, denn $p$ und $q$ teilen beide die Differenz $m^{ed}-m$, also auch ihr Produkt. $\square$

Der Beweis kommt mit dem kleinen Satz von Fermat aus, dem Spezialfall des Satzes von Euler für Primzahlen. Er zeigt auch, warum man zwei verschiedene Primzahlen braucht und warum der Fall $p\mid m$ unproblematisch ist, obwohl dann $m$ keine Einheit in ${\mathbb{Z}}_n$ ist und der Satz von Euler nicht direkt anwendbar wäre.

Warum das sicher ist

Wer $n$ und $e$ kennt, kann $d$ nur bestimmen, wenn er $\phi (n)$ kennt, und das ist so schwer wie das Zerlegen von $n$ in $p·q$: Aus $n$ und $\phi (n)$ ergibt sich $p+q=n-\phi (n)+1$, und $p$, $q$ sind dann die Nullstellen von $x^2-(p+q)x+n$. Für Zahlen $n$ mit mehreren hundert Stellen ist kein schnelles Zerlegungsverfahren bekannt. Wählt man die Nachricht klein und $e$ klein, kann man sie ohne Schlüssel durch Wurzelziehen finden, deshalb füllt man in der Praxis Nachrichten auf („Padding“). Dreht man die Rollen um, entsteht eine digitale Signatur: Wer $d$ kennt, kann $s=m^d$ bilden, und jeder prüft mit dem öffentlichen $e$, ob $s^e\equiv m$ gilt.

Rivest, Shamir und Adleman beschrieben das Verfahren 1977 und veröffentlichten es 1978 in den „Communications of the ACM“. Clifford Cocks hatte bereits 1973 beim britischen GCHQ ein gleichwertiges Verfahren entwickelt, das erst 1997 freigegeben wurde.

Immer neue Aufgaben zu Schlüsseln, Ver- und Entschlüsseln gibt es auf dem Blatt Rechnen in Restklassen (Aufgabenart „RSA mit kleinen Primzahlen“).

Homomorphismen und Ideale

Eine Abbildung $\psi :R\to S$ zwischen Ringen heißt Ringhomomorphismus, wenn $\psi (a+b)=\psi (a)+\psi (b)$ und $\psi (ab)=\psi (a)\psi (b)$ gilt (und $\psi (1)=1$). Sie verträgt sich also mit beiden Rechenarten. Beispiele sind die Restabbildung $\mathbb{Z}\to {\mathbb{Z}}_n$, $a\mapsto a\mathrm{mod}n$ und die Auswertung $ℝ[x]\to ℝ$, $p\mapsto p(2)$. Letztere erklärt, warum $(p·q)(2)=p(2)q(2)$ gilt.

Der Kern $\ker \psi =\{a\mid \psi (a)=0\}$ hat eine besondere Eigenschaft: Er ist eine Untergruppe von $(R,+)$, und mit $a$ im Kern liegt auch $ra$ im Kern, für alle $r\in R$. Solche Teilmengen heißen Ideale.

In $\mathbb{Z}$ ist $n\mathbb{Z}=\{\dots ,-n,0,n,2n,\dots \}$ ein Ideal, und es gibt keine anderen: Jedes Ideal von $\mathbb{Z}$ hat die Form $n\mathbb{Z}$. Beweis: Ist $I\ne \left\{0\right\}$, sei $n$ die kleinste positive Zahl in $I$. Für ein beliebiges $a\in I$ schreibe $a=qn+r$ mit $0\le r<n$ (Division mit Rest). Dann ist $r=a-qn\in I$, und wegen der Minimalität von $n$ ist $r=0$. Also ist $a\in n\mathbb{Z}$. Ein Integritätsbereich, in dem jedes Ideal von einem einzigen Element erzeugt wird, heißt Hauptidealring. Der Faktorring $R/I$ besteht aus den Klassen $a+I$ (siehe Äquivalenzklassen). Für $R=\mathbb{Z}$ und $I=n\mathbb{Z}$ ergibt das genau ${\mathbb{Z}}_n=\mathbb{Z}/n\mathbb{Z}$. Der Satz „${\mathbb{Z}}_n$ ist ein Körper genau für Primzahlen“ bedeutet dann: $n\mathbb{Z}$ ist ein maximales Ideal genau für Primzahlen $n$. („Maximal“ heißt: Zwischen $n\mathbb{Z}$ und $\mathbb{Z}$ liegt kein weiteres Ideal.)

Polynomringe

Für einen Körper $K$ ist $K[x]$, die Menge der Polynome mit Koeffizienten in $K$, ein kommutativer Ring (ein Integritätsbereich). Wie in $\mathbb{Z}$ gibt es eine Division mit Rest (siehe Polynomdivision), also ist $K[x]$ ein Hauptidealring. Der Faktorsatz gilt: $a$ ist genau dann Nullstelle von $p$, wenn $(x-a)$ ein Teiler von $p$ ist. Daraus folgt:

Das stimmt nur über Körpern. Im Ring ${\mathbb{Z}}_8$ hat die Gleichung $x^2=1$ die vier Lösungen $1,3,5,7$ (denn $3^2=9\equiv 1$, $5^2=25\equiv 1$, $7^2=49\equiv 1$), obwohl der Grad nur 2 ist. Im Ring ${\mathbb{Z}}_{15}$ hat $x^2=1$ ebenfalls vier Lösungen, nämlich $1,4,11,14$. Der Grund sind die Nullteiler: $(x-1)(x+1)=0$ kann auch gelten, ohne dass ein Faktor 0 ist.

Ein nichtkonstantes Polynom $p$ heißt irreduzibel, wenn es sich nicht als Produkt zweier nichtkonstanter Polynome schreiben lässt. Ähnlich wie bei Primzahlen gilt: $K[x]/(p)$ ist genau dann ein Körper, wenn $p$ irreduzibel ist. Dabei ist $(p)$ das Ideal aller Vielfachen von $p$. So entstehen neue Körper. Der berühmteste Fall: Das Polynom $x^2+1$ ist über $ℝ$ irreduzibel (keine Nullstelle), und $ℝ[x]/(x^2+1)$ ist der Körper der komplexen Zahlen, denn die Klasse von $x$ erfüllt $x^2=-1$. Mit demselben Verfahren konstruiert man endliche Körper mit $p^k$ Elementen und erhält die Körpererweiterungen, die die Galois-Theorie untersucht.

Typische Fehler

Übungen

Weiter im Studium: Körper mit endlich vielen Elementen und ihre Anwendung in fehlerkorrigierenden Codes stehen auf der Seite Endliche Körper und Codierung, Körpererweiterungen und die Auflösbarkeit von Gleichungen in der Galois-Theorie.

Geschichte: von Zahlen zu Strukturen

Die Gaußsche Zahlentheorie rechnete mit Zahlen wie $a+bi$ (ganze Gaußsche Zahlen) und entdeckte, dass dort ähnliche Gesetze wie in $\mathbb{Z}$ gelten. Richard Dedekind führte 1871 die Begriffe „Körper“ und „Ideal“ ein, um Zerlegungen in algebraischen Zahlbereichen zu retten. Die Bezeichnung „Ring“ kam bei Hilbert (1897). Die heutige Gestalt der Algebra, mit Axiomen statt Beispielen, ist das Werk von Emmy Noether und ihrer Schule (Idealtheorie in Ringbereichen, 1921) und wurde von Bartel van der Waerdens Lehrbuch Moderne Algebra (1930/31) verbreitet. Évariste Galois hatte schon um 1830 endliche Körper betrachtet, die deshalb heute Galois-Felder heißen.

Häufige Fragen

Quellen und weiterführende Literatur

• Wikipedia: Ring (Algebra)
• Wikipedia: Körper (Algebra)
• Siegfried Bosch: Algebra, Springer Spektrum, Berlin.
• Gerd Fischer, Reinhard Sacher: Einführung in die Algebra, Teubner, Stuttgart.
• Bartel L. van der Waerden: Moderne Algebra, Springer, Berlin 1930/31.
• Emmy Noether: Idealtheorie in Ringbereichen, Mathematische Annalen 83 (1921).