Restklassenkorper

3.3 Restklassenkörper

3.3.1 Existenz

Für den Übergang von einem Restklassenring $(Rm,+, ⋅)$ zu einem Restklassenkörper muß man zu jedem $r ∈ Rm ∖{0}$ das Vorhandensein eines multiplikativ inversen Elements $−1 [r]m$ , mit $[r]m ⋅[r]m−1 = [1]m$ , fordern. Wir nehmen die Antwort vorweg und proklamieren, daß es ein solches Element in $(Rm,+,⋅)$ nur dann gegeben kann, wenn $m$ und $r$ teilerfremd sind [PW72, Satz 6.4]. Bezieht man diese Aussage z. B. auf $ℤ∗ = ℤm ∖{0} = {1,2,3,...,m − 1} m$ , dann müssen (wenn keine weiteren Forderungen an $m$ gestellt werden) alle Elemente $r$ , für die $gcd(r,m) = 1$ nicht erfüllt werden kann, ausgeschlossen werden. Sowohl im allgemeinen als auch speziellen Fall von $∗ ℤ m$ ist diese Einschränkung grundsätzlich hinfällig, wenn es sich bei $m$ um ein Primelement handelt (ein vollständiges Restklassensystem) – in Bezug auf $∗ ℤ m$ also um eine Primzahl $p ∈ℙ$ , weshalb $Fq := ℤp$ (mit $q= p$ ). Im Fall des Ausschlusses von Elementen (ein reduziertes Restklassensystem) ist die Anzahl der teilerfremden Zahlen durch EULER’s Totient-Funktion $ϕ(m)$ bestimmt und so die Ordnung der multiplikativen Gruppe $|ℤ ∗m|= ϕ(m )$ , d. h. $Fq ⊆ ℤm$ (mit $q = ϕ(m) +1$ ).

Beweis Ist $m$ kein primes Element, dann läßt es sich mindestens in zwei Faktoren $r,s ∈ Rm$ zerlegen (die nicht Vielfache von $m$ sind, also $r,s mod m ⁄= 0$ ). Da nun $m mod m = 0$ ist, gilt für die Restklassenmultiplikation $[r]m ⋅[s]m = [m ]m = 0$ . Soll aber $[r]m$ eine inverse Restklasse $[r]−m1$ besitzen, dann kann man beide Seiten des Produktes mit $[r]m−1$ multiplizieren.

[r]m−1[r]m ⋅[s]m = [s]m = [r]m−1[m ]m = 0 ◟--◝◜--◞ e(⋅)=1

$[s]m$ ist aber nach Voraussetzung nicht $0$ , demzufolge kann ein Inverses zu $[r]m$ für den Fall dieser Zerlegung nicht existieren.

Im Gegenzug bleibt noch nachzuweisen, daß, wenn $m$ ein Primelement ist, für jede Restklasse $[r] m$ aus $Rm$ ein inverses Element $−1 [r]m$ auch wirklich existiert. Zu diesem Zweck betrachten wir alle $[r]m ∈ Rm$ , ausgenommen die Restklasse $[1]m$ , welche bei der Inversion auf sich selbst abgebildet wird. Da wegen der Modulo-Reduktion (wir verwenden jetzt wieder den Vertreter der Restklasse) immer $m > r$ gilt, kann nur $r$ ein Teiler von $m$ sein und nicht umgekehrt. Aber auch dies ist nicht möglich, wenn nach Voraussetzung $m$ relativ prim zu $r$ ist. Deshalb kann der größte gemeinsame Teiler von $r$ und $m$ nur das Einselement sein. Berücksichtigt man jetzt noch die aus dem euklidischen Algorithmus stammende Erkenntnis (Satz von BéZOUT, vgl. Abschnitt 4.1), daß der größte gemeinsame Teiler $d = gcd (r,s)$ zweier Elemente $r,s$ in der Form $d = αr+ β s$ mit $α,β ∈ ℤ$ darstellbar ist, dann gilt:

Das inverse Element von $[r] m$ ist demzufolge

[r] −1 = [α] , m m

wobei dessen Berechnung z. B. mit Hilfe des erweiterten euklidischen Algorithmus (siehe Abschnitt 4.1.4) möglich ist.¹⁹

3.3.2 Multiplikative Gruppe

Da es sich bei den Restklassenkörpern um spezifische GALOIS-Körper handelt, kann man einige Formeln von Abschnitt 2.2 konkretisieren. Im folgenden sollen deshalb die Körperelemente und deren Ordnung im Zusammenhang mit der multiplikativen Gruppe $F∗ q$ betrachtet werden.

Ordnung von Elementen Abgesehen von den allgemein geltenden Ordnungsrelationen (siehe Abschnitt 2.1) gibt es speziell für den Restklassenkörper $ℤp$ noch eine erwähnenswerte Ausdrucksmöglichkeit für die von einem Körperelement generierte zyklische Untergruppe:

n k | 〈r〉= {r mod (r − 1)|n∈ ℕ, r ∈ ℤ}.

(3.4)

Einsichtig wird die Schreibweise sofort, wenn man sie für jeden Exponent $n$ expandiert.²⁰

Kleiner Satz von Fermat Eine für die praktische Anwendung von Restklassenkörpern sehr wichtige Folgerung aus Gleichung 2.10 ist der (für den Restklassenkörper $ℤp$ geltende) kleine Satz von FERMAT [PD75, II]. Er resultiert sofort aus $rq−1 ≡ 1 (mod m)$ , wenn man berücksichtigt, daß die Ordnung der multiplikativen Gruppe $ℤ ∗= ℤp ∖{0} = {1,2,3,...,p− 1} p$ genau $q− 1= p − 1$ ist.

rp−1 ≡ 1 (mod p)

(3.5)

Aus dieser Kongruenz kann man wegen $0≡ p (mod p)$ außerdem ableiten, daß $p$ stets ein Teiler von $rp−1− 1$ ist.²¹

rp−1− 1 = np ≡ 0 (mod p)

(3.6)

Obwohl der kleine Satz von FERMAT ursprünglich auf $ℤp$ bezogen war, wird sein Name oft auch in Verbindung mit Ausgangsformel 2.10 verwendet (siehe zum Beispiel [FHLM04]) — also ganz allgemein bezogen auf den endlichen Körper $Fq$ . Deshalb sollen an dieser Stelle noch weitere Berechnungsmöglichkeiten erwähnt sein, welche sich direkt aus $q−1 r = 1$ ergeben.

Multiplikation mit $−1 r$ führt z. B. zur Möglichkeit ein Element zu invertieren.
Multiplikation mit $r2$ gibt uns eine weitere Ausdrucksmöglichkeit für das Quadrat eines Elements. $r2 = rq+1$
Für einige Spezialfälle ermöglicht der kleine Satz von FERMAT sogar das Ziehen der Quadratwurzel aus einem Element.
1. Beispielsweise kann man im Erweiterungskörper $F2n$ (vgl. Abschnitt 3.4), in welchem $q = 2n$ ja immer gerade ist, direkt folgende Formel angeben: $√- √ -- q r = rq = r2 = r2n−1$
2. Aber auch im Körper $Fp$ kann man, zumindest für den Fall $p ≡ 3 mod 4$ , eine einfache Lösung präsentieren:²² $√r = rp+14-(mod p).$
  
  Mit einer kurzen Probe läßt sie sich schnell verifizieren:
  $( p+1)2 p+1 √ -p+1 √-2-p−1 √ -2 r 4 = r 2 = r = r r = r = r (mod p).$

Satz von Wilson Betrachtet man die multiplikative Gruppe eines Restklassenkörpers $ℤ p>2$ , so handelt es sich bei den Zahlen $r = 1,2,...,p− 1$ um die $p− 1$ Nullstellen $α$ des Polynoms $p−1 φ(x)= x − 1 (mod p )$ . Anwendung von Gleichung 2.15 auf $∗ ℤp$ führt folgerichtig zum Satz von WILSON [Sho05, 2.8.1], [PD75, II], [Bun08, 2].²³

(p − 1)!≡ − 1 ≡ p− 1 (mod p)

(3.7)

Satz von EULER L. EULER hat für natürliche Zahlen eine sogenannte Totient-Funktion $ϕ(m)$ definiert, welche die Anzahl der positiven Zahlen (größer als $0$ und kleiner als $m$ ) teilerfremd zu $m$ ausdrückt.²⁴ Mit Hilfe dieser Funktion hat er FERMAT’s kleinen Satz folgendermaßen verallgemeinert [Sho05, 2.6], [Bun08, 2], [PD75, II]:

Sind zwei Zahlen $r,m ∈ ℕ$ relativ prim zueinander, d. h. sie haben keinen gemeinsamen Teiler (und so ist $gcd(r,m)= 1$ ), dann gilt:

rϕ(m) ≡ 1 (mod m).

(3.8)

Der Beweis ist mit den Betrachtungen von Abschnitt 2.1 zur Ordnung der multiplikativen Gruppe in $ℤm$ zu erbringen. Danach entspricht die Gruppenordnung $|ℤ ∗m|$ der Anzahl invertierbarer Elemente (solche mit $gcd (r,m) = 1$ ), d. h. mit EULER’s Totient-Funktion genau $∗ |ℤm|= ϕ(m)$ .²⁵ Berücksichtigt man jetzt noch die Gruppen nach Formel 2.10, dann bestätigt sich EULER’s Satz in Form von Gleichung 2.9.

∗ r|ℤm| ≡ 1 (mod m )

Speziell im Restklassenkörper $ℤp$ entspringt aus Kongruenz 3.8 mit $∗ ϕ(p)= |ℤ p|= p− 1$ sofort der kleine Satz von FERMAT.

Für einen speziellen Fall, nämlich das Produkt zweier Primzahlen $m = pq$ , ist es sehr wünschenswert die Totient-Funktion zu kennen.²⁶ Sind $p$ und $q$ nach Voraussetzung Primzahlen, dann können nur die Zahlen (kleiner als $m$ ) gemeinsame Teiler mit $m$ haben, die Vielfache von $p$ oder $q$ sind. Vielfache von $p$ die kleiner als $m$ sind, gibt es aber genau $q− 1$ , was für $q$ äquivalent gilt (nämlich $p,2p,3p,...,(q− 1)p$ und $q,2q,3q,...,(p− 1)q$ ). Somit muß man von den $m − 1$ Zahlen kleiner als $m$ genau $p − 1+ q− 1 = p+ q− 2$ subtrahieren, was zu

führt.²⁷ In ähnlicher Art und Weise kann man auch die folgende Formel ableiten:

3.3.3 Beispiele

Körper $ℤ2$ Der Körper $F2 := ℤ2$ ist von besonderer praktischer Bedeutung, denn er bildet häufig die Grundlage technischer Realisierungen. Die beiden Elemente von $ℤ2$ werden mit ${[0]2,[1]2}$ oder kürzer mit $0,1$ bezeichnet. Wegen ihrer einfachen Implementierung sind die Operationen in $ℤ2$ besonders effizient.

Die Addition (modulo $2$ ) ist mit

geradezu primitiv und entspricht dem logischen Exklusiv-Oder.²⁸ Wie man sofort sieht, ist das neutrale Element die $0$ und wegen Beziehung 3.9 das additiv Inverse die $1$ . Addition und Subtraktion sind in diesem Sinne gleichwertig, denn es gilt $− 1≡ 1 (mod 2)$ .
Ebenfalls eine einfache Operation ist die Multiplikation, denn sie entspricht dem logischen Und.
Die Division erklärt sich mit Hilfe des inversen Elements in $∗ ℤ2 = ℤ2∖{0 }= {1}$ , welches ja die Bedingung $1 ⋅1− 1 = e(⋅) = 1$ erfüllen muß. Einzig mögliche Schlußfolgerung ist die, daß es sich bei dem inversen Element $1 −1$ um $1$ selbst handelt.

Körper $ℤ5$ Für den Körper $ℤ5$ , also dem Fall einer multiplikativen Gruppe der $∗ |ℤ5|= q − 1= 4$ , gilt für die der Elemente: