Anhang A. Der Restklassenkörper ZPdie Modulo Arithmetik |
Die Menge der Elemente von ZpZ 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. 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.
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.
Das Rechenzeichen für die Bestimmung des Restes einer Division ist "mod". Also läßt sich obiges nun so schreiben
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 AdditionWie 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
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
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:
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
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.
Aus diesen Eigenschaften folgt, daß Zp bezüglich der Addition eine Gruppe ist. Die MultiplikationDie 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.
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:
Für ein neutrales Element N* bezüglich der Multiplikation muß gelten:
und für das Inverse Element A-1 zu A muß gelten:
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:
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
ErgebnisZP* 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
so geschrieben
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:
|
zum
Anfang | Home
Copyright 1999 by Thomas Laubrock |