Anhang A. Der Restklassenkörper ZP

die Modulo Arithmetik

Die Menge der Elemente von Zp

Z ist bekannt als Menge der ganzen Zahlen, samt der definierten Rechenoperationen Addition, Subtraktion und Multiplikation.

Klassifiziert man die ganzen Zahlen nun nach dem Rest bezüglich der Division mit p, erhält man p Klassen; die Klassen der ganzen Zahlen, die dividiert mit p den Rest 0,1,..., p-1 haben. Salopp gesprochen enthält eine Klasse alle ganzen Zahlen, die den gleichen Rest haben; natürlich nur für ein und dasselbe p. Die Gesamtheit dieser Klassen bildet die Menge Zp. Man notiert statt der gesamten Klasse den Repräsentanten, der zwischen 0 und p - 1 liegt, als Elemente von Zp.
Im Weiteren sei nun p eine Primzahl, da dies nötig ist, damit Zp ein Körper ist.

Beispiel:

Gegeben sei p = 17, also besteht Z17 aus den Klassen {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}

Die Klassenzugehörigkeit für 24 in Z17 wird nun folgendermaßen bestimmt.

App.rk.1: Z17 Modulo-Ring

24 / 17 = 1 Rest 7

(Die Schreibweise mit Rest sollte jedem noch aus der Grundschule bekannt sein.)

D.h. in diesem Sinne sind -27, -10, 7, 24, 41, 58,... Repräsentanten der Klasse in Z17, die wir kurz als 7 notieren. Anschaulich läßt sich diese Zahlenmenge wie ein Ring darstellen, zum Addieren wird einfach mit dem Uhrzeigersinn weitergezählt und zum Subtrahieren gegen den Uhrzeigersinn. Nebenstehendes Applet verdeutlicht dies: Einfach '+' oder '-' drücken, um schrittweise zu addieren bzw. zu subtrahieren. Oder in das Textfeld eine Zahl eingeben und 'OK' drücken, um den Rest modulo p bzw. die Klasse dieser Zahl zu finden.
Mathematisch ist der Rest r genau die Zahl, die man zu a · 17 (a Î Z, (a + 1) · 17 > 24 Ù a · 17 <= 24) addieren muß, um die Zahl 24 zu erhalten. Allgemein für eine beliebige Zahl x, gilt


a · p + r = x mit a,p,r,x ÎZ, (a + 1) · p > x Ù a · p <= x

Gl.:rk.1

Das Rechenzeichen für die Bestimmung des Restes einer Division ist "mod". Also läßt sich obiges nun so schreiben

x mod p = r

Gl.: rk.2

 

Betrachtet man nun Obiges, so stehen weiterhin alle ganzen Zahlen Z zur Verfügung. Nur für eine Zahl A größer p ist immer eine kleinere Zahl a zwischen 0 und p-1 zu finden, die das gleiche Element in Zp repräsentiert. Die beiden Zahlen A und a gehören also zur gleichen Klasse. Dies ist ein Vorteil bei der Benutzung von Zp in Computerprogrammen, denn so lassen sich alle Operationen mit relativ kleinen Zahlen, Speicherplatz und Rechenzeit sparend, ausführen. Das gleiche gilt natürlich entsprechend für Zahlen kleiner Null.

Anmerkung: Einigen Lesern wird es ungewöhnlich erscheinen, daß ein Element einer Menge mehrere Repräsentanten hat. Intuitiv benutzt man immer den kleinsten positiven Repräsentanten, genauer: den Repräsentanten zwischen 0 und p-1. Im Folgenden wird aber dies nicht direkt vorausgesetzt, und daher scheint die Formulierung teilweise ein wenig umständlich.

Die Addition

Wie schon in der Beschreibung zum Applet angedeutet, lassen sich zwei Zahlen aus Zp auch addieren. Diese Verknüpfungen, werden die Klassen mit ihrem Repäsentanten aus {0, 1,..., p-1} identifiziert, entsprechen genau denen für Z, nur daß das Ergebnis anschließend mod p gerechnet wird. So ist z.B. das Ergebnis der Addition zweier ganzer Zahlen einfach in das Textfeld von Applet (App.rk.1) einzugeben, um das Ergebnis in Zp zu bestimmen.

Daß die Addition assoziativ ist, also

((a + b) + c ) mod p = (a + (b + c)) mod p

Gl.: rk.8

ist anhand der Darstellung in App.rk.1 und der Assoziativität von Z leicht ersichtlich. Denn die Anzahl der Schritte, die im Kreis gegangen werden, bleiben gleich.

Eine Zahl N aus Z ist genau dann ein Repräsentant des neutralen Elementes bezüglich der Addition, wenn gilt

N mod p = 0, also N ein vielfaches von p

Gl.: rk.5

Beispiel

0 mod 17 = 0
34 mod 17 = 0

Ist a ein Repräsentant von A, so ist jedes a' aus Z für das gilt: a + a' = np mit n aus Z, also für das gilt:

(a+a') mod p = 0  

ein Repräsentant des zu A inversen Elementes. Ist N aus Z mit N - p < a <= N ein Repräsentant des neutralen Elements, so ist mit

a' := N - a, mit a Î{0, 1,..., p-1} Gl.: rk.6

ein Repräsentant des zu A inversen Elementes gefunden

oder kürzer:

Im folgenden werden bei Additionen die Klassen stets durch ihre Repräsentanten aus {0,1,...,p-1} repräsentiert. D.h. das neutrale Element bezüglich der Addition wird durch 0 repräsentiert.
Das inverse Element bezüglich der Addition zu a in Zp ist

a' := p - a.

Gl.: rk.6.a

Beispiel für A = 10 aus Z17 also p = 17:

      a' := 17 - 10 = 7,

also

       (a + a') mod 17 = (10 + 7) mod 17 = 0

oder

        (10 + 24) mod 17 = 0.

Aus diesen Eigenschaften folgt, daß Zp bezüglich der Addition eine Gruppe ist.

Die Multiplikation

Die Struktur Zp bildet bezüglich der Multiplikation keine Gruppe, da sich für das Element 0 kein Inverses finden läßt. Es sei nun Zp* = {a Î Zp \ {0} }. So läßt sich jede Multiplikation in Zp*, wie auch in Z, als Vielfachsumme schreiben.

Beispiel:

   

(3 · 5) mod p = (5 + 5+ 5) mod p = 15 mod p

Gl.: rk.7

Da für die Addition die Assoziativität oben gezeigt wurde, ist auch die Multiplikation aus gleichen Gründen assoziativ. Offensichtlich ist die Multiplikation auch kommutativ.

Bemerkung: Die Multiplikation ist unabhänig von der Wahl des Repräsentanten:

((a + np)(b + mp)) mod p = (ab + amp + bnp + npmp) mod p =(ab) mod p, mit n, m Î Z  

Für ein neutrales Element N* bezüglich der Multiplikation muß gelten:

N* = np + 1 mit n ÎZ
also: N* mod p = 1 ,

so daß a(np + 1) mod p = (anp + a) mod p = a mod p
also: (a · N*) mod p = a mod p

Gl.: rk.9

und für das Inverse Element A-1 zu A muß gelten:

(A-1 · A) mod p = 1

Gl.rk.10

Da ggT(a,p) = 1 für alle a aus {0,1,..,p-1}, denn p ist eine Primzahl, dann existieren ein n, m aus Z mit na+mp=1 ([BSW98], S. 117). Damit ist a':= n mod p das multipikative Inverse zu a. Denn:

(aa') mod p = (an) mod p = (1-mp) mod p = 1  

Wie oben beschrieben existiert für 0 kein inverses Element, weiter ist es zwingend erforderlich, daß p eine Primzahl ist, da es sonst ein a Î Zp* gibt mit ggT(a, p)>1 und damit keine Inverse.

Beispiel: Für Z22* ist zu a = 11 keine multiplikative Inverse zu finden. Das liegt daran, daß 11 nicht teilerfremd zu 22 ist. So ist (b · 11) mod 22 immer gleich 0 oder 11 und nie 1, mit b Î Z. Zu einer Primzahl p ist eine Zahl a, die größer 0 und kleiner p ist, immer teilerfremd, also ggT(a, p) = 1.

Offensichtlich gilt das Distributivgesetz: (a(b + c)) mod p = (ab + bc) mod p

 

Ergebnis

ZP* ist auch bezüglich der Multiplikation eine Gruppe, also bildet Zp einen Körper. Und über Körpern können elliptische Kurven gezeichnet werden.

Im Körper Zp gelten in oben definiertem Sinne die gleichen Grundrechengesetze wie im Körper der rationalen Zahlen, daher werden hier auch die gleichen Rechenzeichen benutzt.

Weiter ist noch eine Vereinfachung der Schreibweise zu definieren. Damit nicht jede Operation wieder Modulo gerechnet werden muß, sei von nun an z.B. folgende Gleichung

(((a + b)mod p)· c )mod p = (((d · e)mod p) + f)mod p

Gl.: rk.3

so geschrieben

(a + b) · c = d · e + f      (mod p)

Gl.: rk.4

 

Für die Operationen auf einem Restklassenkörper lassen sich, da der Körper eine endliche Anzahl an Elementen hat, auch Tabellen zur Berechnung anlegen:

Beispiel für Z17:

+ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0
2 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1
3 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1 2
4 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1 2 3
5 5 6 7 8 9 10 11 12 13 14 15 16 0 1 2 3 4
6 6 7 8 9 10 11 12 13 14 15 16 0 1 2 3 4 5
7 7 8 9 10 11 12 13 14 15 16 0 1 2 3 4 5 6
8 8 9 10 11 12 13 14 15 16 0 1 2 3 4 5 6 7
9 9 10 11 12 13 14 15 16 0 1 2 3 4 5 6 7 8
10 10 11 12 13 14 15 16 0 1 2 3 4 5 6 7 9 9
11 11 12 13 14 15 16 0 1 2 3 4 5 6 7 8 9 10
12 12 13 14 15 16 0 1 2 3 4 5 6 7 8 9 10 11
13 13 14 15 16 0 1 2 3 4 5 6 7 8 9 10 11 12
14 14 15 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13
15 15 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
16 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Abb.rk.1: Additionen in Z17

 

· 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2 0 2 4 6 8 10 12 14 16 1 3 5 7 9 11 13 15
3 0 3 6 9 12 15 1 4 7 10 13 16 2 5 8 11 14
4 0 4 8 12 16 3 7 11 15 2 6 10 14 1 5 9 13
5 0 5 10 15 3 8 13 1 6 11 16 4 9 14 2 7 12
6 0 6 12 1 7 13 2 8 14 3 9 15 4 10 16 5 11
7 0 7 14 4 11 1 8 15 5 12 2 9 16 6 13 3 10
8 0 8 16 7 15 6 14 5 13 4 12 3 11 2 10 1 9
9 0 9 1 10 2 11 3 12 4 13 5 14 6 15 7 16 8
10 0 10 3 13 6 16 9 2 12 5 15 8 1 11 4 14 7
11 0 11 5 16 10 4 15 9 3 14 8 2 13 7 1 12 6
12 0 12 7 2 14 9 4 16 11 6 1 13 8 3 15 10 5
13 0 13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4
14 0 14 11 8 5 2 16 13 10 7 4 1 15 12 9 6 3
15 0 15 13 11 9 7 5 3 1 16 14 12 10 8 6 4 2
16 0 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Abb.rk.1: Additionen in Z17
zum Anfang | Home
Copyright 1999 by Thomas Laubrock
Zurück zur letzen Seite nächste Seite