Ring- und Körperrechner

Was ist ein Ring in der abstrakten Algebra?

Ein Ring gehört zu den grundlegenden Strukturen der abstrakten Algebra. Formal ist ein Ring (R, +, ×) eine Menge R mit zwei Verknüpfungen, für die drei Axiomgruppen gelten: (1) (R, +) ist eine abelsche Gruppe — die Addition ist assoziativ, kommutativ, besitzt das neutrale Element 0 und zu jedem Element ein additives Inverses; (2) die Multiplikation ist assoziativ; (3) es gelten die Distributivgesetze. Ist auch die Multiplikation kommutativ, heißt R kommutativer Ring. Existiert ein multiplikatives neutrales Element 1 ≠ 0, spricht man von einem Ring mit Einselement.

Bekannte Ringe sind die ganzen Zahlen ℤ, die rationalen Zahlen ℚ, die reellen Zahlen ℝ, die komplexen Zahlen ℂ, Polynomringe R[x] und Matrizenringe M_n(R). Die ganzen Zahlen modulo n, geschrieben als ℤₙ oder ℤ/nℤ, bilden für jedes n ≥ 2 einen kommutativen Ring mit Einselement.

Ringaxiome im Überblick

Axiom	Eigenschaft	Gilt in ℤₙ?
A1	Assoziativität der Addition: (a+b)+c = a+(b+c)	Immer
A2	Kommutativität der Addition: a+b = b+a	Immer
A3	Neutrales Element der Addition: a + 0 = a	Immer
A4	Additives Inverses: a + (-a) = 0	Immer
M1	Assoziativität der Multiplikation: (ab)c = a(bc)	Immer
M2	Kommutativität: ab = ba	Immer
M3	Neutrales Element der Multiplikation: 1·a = a·1 = a	Immer
D	Distributivität: a(b+c) = ab + ac	Immer

Was ist ein Integritätsbereich?

Ein Integritätsbereich ist ein kommutativer Ring mit Einselement ohne Nullteiler. Ein Nullteiler ist ein Element a ≠ 0, für das ein b ≠ 0 mit ab = 0 existiert. In ℤₙ ist a genau dann Nullteiler, wenn ggT(a, n) > 1 und a ≠ 0 gilt. Beispiel in ℤ₆: 2 × 3 = 6 ≡ 0 (mod 6). Daher sind 2 und 3 Nullteiler und ℤ₆ ist kein Integritätsbereich. Für Primzahlen n gilt ggT(a, n) = 1 für alle 1 ≤ a ≤ n−1; somit ist ℤ_p ein Integritätsbereich.

Was ist ein Körper?

Ein Körper ist ein kommutativer Ring mit Einselement, in dem jedes Element ungleich null ein multiplikatives Inverses besitzt. Klassische Beispiele sind ℚ, ℝ und ℂ. Unter den Restklassenringen ℤₙ ist ℤ_p genau dann ein Körper, wenn p eine Primzahl ist, denn dann gilt für jedes a ≠ 0 die Bedingung ggT(a, p) = 1 und damit existiert a⁻¹ mod p. Jeder Körper ist ein Integritätsbereich; für endliche Ringe gilt auch die entsprechende Umkehrung für Divisionsringe nach dem kleinen Satz von Wedderburn.

Einheiten, Nullteiler, nilpotente und idempotente Elemente

Vier besondere Elementklassen beschreiben die Struktur von ℤₙ:

• Einheiten: Elemente a mit ggT(a, n) = 1. Sie bilden die multiplikative Gruppe (ℤₙ)* der Ordnung φ(n). In einem Körper ist jedes Element ungleich null eine Einheit.
• Nullteiler: Elemente a ≠ 0 mit ggT(a, n) > 1. Gilt ab ≡ 0, sind a und b Nullteiler. Nullteiler fehlen genau dann, wenn n prim ist.
• Nilpotente Elemente: Elemente a, für die a^k ≡ 0 (mod n) mit einer positiven ganzen Zahl k gilt. In ℤₙ ist a genau dann nilpotent, wenn jeder Primfaktor von n auch a teilt. In einem Körper ist nur 0 nilpotent.
• Idempotente Elemente: Elemente a mit a² ≡ a (mod n). Dazu gehören immer 0 und 1; für zusammengesetzte n treten weitere auf. Nach dem chinesischen Restsatz ist ihre Anzahl 2^k, wobei k die Zahl der verschiedenen Primfaktoren von n ist.

Endliche Körper — Galois-Körper GF(p^k)

Die einzigen endlichen Körper sind die Galois-Körper GF(q), auch 𝔽_q, wobei q = p^k für eine Primzahl p und k ≥ 1 gilt. Für k = 1 ist GF(p) = ℤ_p. Bei k > 1 entsteht GF(p^k) nicht als ℤ_p^k, sondern als Quotientenring ℤ_p[x]/(f(x)) mit einem über ℤ_p irreduziblen Polynom f vom Grad k. Genau damit arbeitet der Tab Polynomring.

Galois-Körper sind für moderne Technik unverzichtbar: Die AES-Verschlüsselung rechnet in GF(2⁸), Reed-Solomon-Codes für QR-Codes und CDs nutzen ebenfalls GF(2⁸) und die Elliptische-Kurven-Kryptografie arbeitet über GF(p) oder GF(2^k).

Polynomringe ℤ_p[x]

Ist p prim, besteht der Polynomring ℤ_p[x] aus allen Polynomen mit Koeffizienten in ℤ_p. Er ist ein Integritätsbereich. Man kann Polynomdivision durchführen, ggT mit dem euklidischen Algorithmus berechnen und Polynome in irreduzible Faktoren zerlegen. Der Quotient nach einem irreduziblen Polynom f(x) vom Grad k ergibt den endlichen Körper GF(p^k).

Referenztabelle: Struktur von ℤₙ für häufige n

n	Ring	Komm. Ring	Integritätsbereich	Körper	Einheiten	Nullteiler
2	Ja	Ja	Ja	Ja	{1}	keine
4	Ja	Ja	Nein	Nein	{1,3}	{2}
5	Ja	Ja	Ja	Ja	{1,2,3,4}	keine
6	Ja	Ja	Nein	Nein	{1,5}	{2,3,4}
7	Ja	Ja	Ja	Ja	{1,2,3,4,5,6}	keine
12	Ja	Ja	Nein	Nein	{1,5,7,11}	{2,3,4,6,8,9,10}

Anwendungen in Codierungstheorie und Kryptografie

• RSA-Kryptografie: Die Schlüsselerzeugung arbeitet in (ℤ_φ(n), +, ×); für d = e⁻¹ mod φ(n) ist die Struktur der Einheitengruppe nötig.
• Diffie-Hellman / ElGamal: Die Sicherheit beruht auf dem diskreten Logarithmus in der zyklischen Einheitengruppe (ℤ_p)* für große Primzahlen p.
• AES: Die Schritte AddRoundKey, SubBytes und MixColumns arbeiten in GF(2⁸) = ℤ₂[x]/(x⁸+x⁴+x³+x+1).
• Reed-Solomon-Codes: Fehlerkorrektur mittels Polynomarithmetik über endlichen Körpern, eingesetzt in QR-Codes, CDs, DVDs und Weltraumtelemetrie.
• BCH- und LDPC-Codes: werden mithilfe der Eigenschaften von Polynomringen über endlichen Körpern konstruiert.
• Elliptische-Kurven-Kryptografie (ECC): Die Punktgruppe einer elliptischen Kurve über GF(p) oder GF(2^k) liefert das Problem des diskreten Logarithmus für moderne TLS-Verfahren.