Algebra fur Informatiker [PDF]

Zitiervorschau

Algebra fur Informatiker Johannes Buchmann 6. August 1996

Inhaltsverzeichnis 1 Elementare Zahlentheorie

4

1.1 Naturliche Zahlen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 1.2 Ganze Zahlen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6 1.3 Teilbarkeit : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 1.4 Division mit Rest und Komplexitat arithmetischer Operationen : : : : : : : 9 1.5 Groter gemeinsamer Teiler : : : : : : : : : : : : : : : : : : : : : : : : : : : 10 1.6 Eindeutige Primfaktorzerlegung : : : : : : : : : : : : : : : : : : : : : : : : : 13 1.7 Kongruenzen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14

2 Gruppen

17

2.1 Algebraische Struktur : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 17 2.2 Halbgruppen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 19 2.3 Direkte Produkte : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 21 2.4 Faktorhalbgruppen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 21 2.5 Neutrale Elemente : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 22 2.6 Invertierbare Elemente : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 23 2.7 Gruppen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 23 2.8 Beispiele von Gruppen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 24 2.9 Gruppentafeln : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 25 2.10 Zyklische Gruppen und Elementordnung : : : : : : : : : : : : : : : : : : : : 27 2.11 Berechnung der Elementordnung : : : : : : : : : : : : : : : : : : : : : : : : 29 1

Version 6. August 1996

2

2.12 Berechnung diskreter Logarithmen : : : : : : : : : : : : : : : : : : : : : : : 31 2.13 Untergruppen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 32 2.14 Gruppenhomomorphismen : : : : : : : : : : : : : : : : : : : : : : : : : : : : 33 2.15 Der Satz von Lagrange : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 35 2.16 Anwendung des Satzes von Lagrange : : : : : : : : : : : : : : : : : : : : : : 36 2.17 Normalteiler und Faktorgruppen : : : : : : : : : : : : : : : : : : : : : : : : 37 2.18 Erzeugendensysteme : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 38 2.19 Operation von Gruppen auf Mengen : : : : : : : : : : : : : : : : : : : : : : 38 2.20 Die symmetrische Gruppe Sn : : : : : : : : : : : : : : : : : : : : : : : : : : 39 2.21 Freie Gruppen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 41

3 Ringe

43

3.1 Ringbegri : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 43 3.2 Polynomringe : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 44 3.3 Ideale, Restklassenringe : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 46 3.4 Homomorphiesatz : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 48 3.5 Quotientenkorper und Primkorper : : : : : : : : : : : : : : : : : : : : : : : 49 3.6 Nullstellen, Dierentiation und Interpolation von Polynomen : : : : : : : : 50 3.7 Euklidische Ringe : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 52 3.8 Teilbarkeit : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 52 3.9 ZPE-Ringe : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 53 3.10 Irreduzibilitatstests : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 55 3.11 Primideale, maximale Ideale : : : : : : : : : : : : : : : : : : : : : : : : : : : 56 3.12 Faktorisierung von Polynomen : : : : : : : : : : : : : : : : : : : : : : : : : 58 3.13 Algorithmus von Berlekamp : : : : : : : : : : : : : : : : : : : : : : : : : : : 61

Version 6. August 1996

3

4 Lineare Algebra

65

4.1 Einfuhrung : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 65 4.2 Moduln und Homomorphismen : : : : : : : : : : : : : : : : : : : : : : : : : 66 4.3 Kern und Bild von Homomorphismen : : : : : : : : : : : : : : : : : : : : : 69 4.4 Smith-Normalform : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 77 4.5 Normalformen von Moduln : : : : : : : : : : : : : : : : : : : : : : : : : : : 82

5 Grobner Basen

90

5.1 Einfuhrung : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 90 5.2 Monomordnungen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 91 5.3 Ein Divisionsalgorithmus in K [x1 ; : : :; xn ] : : : : : : : : : : : : : : : : : : : 92 5.4 Monomiale Ideale und Dicksons Lemma : : : : : : : : : : : : : : : : : : : : 94 5.5 Hilbertscher Basissatz und Grobnerbasen : : : : : : : : : : : : : : : : : : : 95 5.6 Eigenschaften von Grobnerbasen : : : : : : : : : : : : : : : : : : : : : : : : 96 5.7 Buchbergers Algorithmus : : : : : : : : : : : : : : : : : : : : : : : : : : : : 99 5.8 Anwendungen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 102 5.8.1 Idealmitgliedschaft : : : : : : : : : : : : : : : : : : : : : : : : : : : : 102 5.8.2 Teilmengenbeziehungen zwischen Idealen : : : : : : : : : : : : : : : 102 5.8.3 Idealgleichheit : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 102 5.8.4 Losen von Gleichungssystemen : : : : : : : : : : : : : : : : : : : : : 102

Kapitel 1

Elementare Zahlentheorie In diesem Kapitel werden wichtige Eigenschaften der ganzen Zahlen besprochen. Die Begrie und Ergebnisse dieses Kapitels nehmen allgemeinere Begrie und Ergebnisse, die im Lauf der Vorlesung eingefuhrt bzw. bewiesen werden, im Spezialfall vorweg. Sie dienen darum spater als Beispielmaterial.

1.1 Naturliche Zahlen Ich setze voraus, da die Menge IN der naturlichen Zahlen bekannt ist. Diese Menge wird durch die Axiome von Peano charakterisiert, namlich 1. 2. 3. 4. 5.

1 ist eine naturliche Zahl. Jede naturliche Zahl a hat einen Nachfolger a+ in IN. Es gibt keine naturliche Zahl mit dem Nachfolger 1. Stimmen die Nachfolger zweier naturlicher Zahlen a und b uberein, so gilt a = b. Die einzige Menge von naturlichen Zahlen, die die Zahl 1 enthalt und die mit jedem Element a auch dessen Nachfolger enthalt, ist IN selbst.

Das letzte Axiom heit Prinzip der vollstandigen Induktion . Dieses Prinzip wird benutzt, um Eigenschaften der naturlichen Zahlen zu beweisen und neue Begrie zu de nieren. Man kann beispielsweise zeigen, da sich auf genau eine Art jedem Paar x; y naturlicher Zahlen eine naturliche Zahl, x+y genannt, so zuordnen lat, da

x + 1 = x+; x 2 IN; und

x + y + = (x + y )+ ; x; y 2 IN 4

Version 6. August 1996

5

gilt. Die Zahl x + y heit Summe von x und y . Statt a+ schreibe ich ab sofort a + 1. Fur alle naturlichen Zahlen a; b; c gilt das Assoziativgesetz und das Kommutativgesetz Auerdem gilt:

(a + b) + c = a + (b + c)

(1.1)

a + b = b + a:

(1.2)

Aus a + b = a + c folgt b = c:

(1.3)

Statt a1 + a2 + : : : + ak schreibt man kurz

Pk a .

i=1

i

Weiter kann man jedem Paar x; y naturlicher Zahlen auf genau eine Weise ihr Produkt x
y oder xy so zuordnen, da x
1 = x; x 2 IN und x(y + 1) = xy + x gilt. Fur alle naturlichen Zahlen a; b; c gilt dann das Assoziativgesetz das Kommutativgesetz und das Distributivgesetz Ferner gilt:

(ab)c = a(bc);

(1.4)

ab = ba

(1.5)

a(b + c) = ab + ac:

(1.6)

Aus ab = ac folgt b = c

(1.7)

Qk

Dies nennt man Kurzungsregel . Statt a1 a2


ak schreibt man kurz ai . Ist hierbei a1 = i=1 a2 = : : : = ak so schreibt man a1 a2


ak = ak . Gilt a = b + u fur naturliche Zahlen a; b; u, so schreibt man a > b oder b < a und sagt, da a groer als b ist oder da b kleiner als a ist. Wiederum beweist man durch vollstandige Induktion, da genau eine der Relationen

a < b; a = b; a > b (1.8) erfullt ist. Weiter gilt fur alle naturlichen Zahlen a; b; c: Aus a < b und b < c folgt a < c: (1.9) Aus a < b folgt a + c < b + c: (1.10) Aus a < b folgt ac < bc: (1.11) Ist a > b so wird die eindeutig bestimmte Losung der Gleichung a = b + u mit a ; b bezeichnet. Fur \a < b oder a = b" schreibt man kurz a  b. Fur \a > b oder a = b" schreibt man kurz a  b. Weiter gilt der sogenannte Wohlordnungssatz.

Version 6. August 1996

6

1.1.1. Satz Jede nicht leere Menge naturlicher Zahlen enthalt eine kleinste Zahl, d.h. eine solche, die kleiner ist als alle anderen Zahlen der Menge. Um mit naturlichen Zahlen rechnen zu konnen, braucht man eine Darstellung . Normalerweise benutzt man die Dezimaldarstellung. Computer verwenden die Binardarstellung. Etwas allgemeiner fuhre ich hier die g -adische Darstellung ein, wobei g eine feste naturliche Zahl ungleich 1 ist. Man braucht zuerst g viele verschiedene Zeichen. Wenn g = 2 ist, also bei der Binardarstellung, benutzt man die Zeichen 0; 1. Wenn g = 10 ist, also bei der Dezimaldarstellung, nimmt man die Zeichen 0; 1; 2; 3; 4; 5; 6; 7; 8; 9. Wenn g = 16 ist, also bei der Hexadezimaldarstellung, benutzt man die Zeichen 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; A; B; C; D; E; F . Sei  die Menge der g verschiedenen Zeichen. Mit  bezeichne ich die Menge aller endlichen Folgen von Zeichen aus  einschlielich der leeren Folge, fur die ich " schreibe. Die Elemente aus  heien auch Strings uber . Den naturlichen Zahlen a < g seien verschiedene Zeichen der Menge  zugeordnet. Die naturliche Zahl 1 wird durch das Zeichen 1 dargestellt. Zusatzlich gibt es noch das Zeichen 0 in  dem keine naturliche Zahl entspricht. Die Menge  enthalt also immer die Zeichen 0; 1. Die von 0 verschiedenen Elemente von  werden mit den durch sie dargestellten Zahlen identi ziert. Jedem String s = s1 s2 : : :sk 2  ; k  1; s1 6= 0 wird die naturliche Zahl k X

i=1 si 6=0

si g k;i

zugeordnet. Dann wird jede naturliche Zahl durch genau einen String uber  dargestellt. Die Elemente aus  heien Ziern. Pk s gk;i ist bijektiv. Die Abbildung ( ; 0)   ! IN; s1 s2 : : :sk 7! i i=1 si 6=0

1.2 Ganze Zahlen Die Menge der naturlichen Zahlen wird folgendermaen zur Menge der ganzen Zahlen erganzt. Man betrachtet die Menge aller Paare (a; b) von naturlichen Zahlen. Man stellt sich vor, da (a; b) die ganze Zahl a ; b reprasentiert. Ganze Zahlen haben dann verschiedene Darstellungen. Um dem Rechnung zu tragen, werden Paare identi ziert, die dieselbe ganze Zahl darstellen. Zwei Paare (a; b) und (x; y ) werden aquivalent genannt, wenn a + y = x + b gilt. Dies ist eine A quivalenzrelation. Die Menge der ganzen Zahlen ist die Menge der A quivalenzklassen. Sie wird mit ZZ bezeichnet. Man de niert Addition, Multiplikation und Vergleich ganzer Zahlen folgendermaen. Fur naturliche Zahlen a; b; c; d setzt man (a; b) + (c; d) = (a + c; b + d); (a; b)
(c; d) = (ac + bd; ad + bc) und man schreibt (a; b) < (c; d) oder (c; d) > (a; b); falls a + d < b + c:

Version 6. August 1996

7

Man veri ziert leicht, da diese De nitionen von der Wahl der Vertreter unabhangig sind. Folgendermaen werden einfachere Bezeichnungen fur ganze Zahlen eingefuhrt. Alle Paare (a; a) gehoren zu derselben A quivalenzklasse. Fur diese schreibt man 0. Ist a > b, so bezeichnet man die A quivalenzklasse, die (a; b) enthalt, mit a ; b. Ist a < b, so schreibt man ;(b ; a) fur die A quivalenzklasse, die (a; b) enthalt. Es ist leicht zu sehen, da diese Bezeichnungen wohlde niert sind. Man veri ziert leicht, da die Rechengesetze (1.1) - (1.10) gelten. Alledings gilt nun statt (1.11), wie man ebenfalls leicht veri ziert:

8 > falls c > 0 < ac < bc; Aus a < b folgt > ac = bc = 0; falls c = 0 : ac > bc; falls c < 0:

Auerdem hat fur ganze Zahlen a; b die Gleichung a = b + x stets eine eindeutig bestimmte Losung x, die ebenfalls eine ganze Zahl ist. Fur diese schreibt man auch a ; b. Schlielich gilt ab = 0 genau dann, wenn a oder b gleich 0 ist. Auch die Darstellung ganzer Zahlen wird von der Darstellung naturlicher Zahlen abgeleitet. Die Zahl 0 wird durch das Symbol 0 dargestellt. Es wurde ja vorausgesetzt, da dieses Symbol zu dem Alphabet  gehort. Jede von 0 verschiedene ganze Zahl ist entweder eine naturliche Zahl oder ;a fur eine naturliche Zahl a. Dies liefert unmittelbar die Darstellung der ganzen Zahlen. Bei der Binardarstellung kann das Vorzeichen in einem weiteren Bit gespeichert werden. Die Anzahl der Bits, die notig ist, um eine ganze Zahl z in Binardarstellung zu speichern, ist size(z ) =

(

1 falls z = 0 blog jzjc + 2 falls z 6= 0:

1.3 Teilbarkeit Nun werden elementare arithmetische Begrie und Eigenschaften der ganzen Zahlen eingefuhrt. Eine ganze Zahl a heit Teiler einer ganzen Zahl b, wenn es eine ganze Zahl g gibt, fur die b = ga gilt. Dafur schreibt man kurz a j b (lies: a teilt b). Das Gegenteil wird mit a6 j b (lies: a teilt nicht b) bezeichnet. Das Problem, zu entscheiden, ob a ein Teiler von b ist, wird im Zusammenhang mit der Division mit Rest angesprochen.

(

1.3.1. De nition jaj = ;a;a; aa 1 besitzt wenigstens einen Primteiler. Beweis: Unter allen Teilern r > 1 wahle man den kleinsten aus. Dies geht nach dem

Wohlordnungssatz. Der ausgewahlte Teiler heie t. Wenn t keine Primzahl ist, so besitzt t einen Teiler s mit 1 < s < t. Nach (1.17) ist s auch ein Teiler von a und dies widerspricht der Wahl von t.

1.3.4. Satz Es gibt unendlich viele Primzahlen. Beweis: Angenommen, die Menge IP aller Primzahlen ist endlich. Setze a = Q p + p2IP

1. Nach Satz 1.3.3 besitzt a einenQ Primteiler q . Wenn dieser mit einer Primzahl in IP ubereinstimmt, so gilt q j 1 = a ; p nach (1.18) und damit q = 1. Dies ist aber wegen p2IP q > 1 unmoglich.

Ein zentrales Thema der Zahlentheorie sind die Primzahlen. Es gibt sehr viele interessante algorithmische Probleme im Zusammenhang mit Primzahlen. Mit Hilfe des Siebs des Erathostenes (siehe [10], p.3) kann man z.B. alle Primzahlen unterhalb einer gegebenen Schranke aufzahlen. Dies geht in polynomieller Zeit. Viel schwieriger ist es, zu entscheiden, ob eine gegebene naturliche Zahl eine Primzahl ist (siehe [10], Chapter 4, [3], Chapter 9). Es ist bis jetzt kein deterministischer Polynomzeitalgorithmus bekannt, der diese Entscheidung fallt. Es gibt aber eziente probabilistische Verfahren in polynomieller Zeit.

1.3.5. U bung Ein Primzahlzwilling ist ein Paar (p; q) ungerader Primzahlen mit q =

p + 2. Es ist nicht bekannt, ob es unendlich viele Primzahlzwillinge gibt. Man schreibe ein Programm, das alle Primzahlzwillinge unterhalb einer gegebenen Schranke ausgibt.

Version 6. August 1996

9

1.4 Division mit Rest und Komplexitat arithmetischer Operationen 1.4.1. Satz Zu jedem Paar a; b ganzer Zahlen mit b 6= 0 gibt es genau ein Paar q; r ganzer Zahlen, das die Bedingungen

a = qb + r; 0  r < jbj erfullt.

Beweis: Es genugt, den Fall b > 0 zu betrachten. Es ist dann zu zeigen, da es genau eine ganze Zahl q gibt, fur die qb  a < b(q + 1) gilt. Dies ist gleichbedeutend mit der Bedingung q  a=b < q + 1, welcher genau eine ganze Zahl q genugt.

1.4.2. Beispiel a = ;27, b = ;10 ) q = r = 3. Die arithmetischen Operationen fur ganze Zahlen sind Addition, Subtraktion, Multiplikation und Division mit Rest. Schon aus der Schule sind Verfahren bekannt, wie man ganze Zahlen in Dezimaldarstellung addieren, subtrahieren, multiplizieren und mit Rest dividieren kann. Entsprechende Verfahren lassen sich fur g -adisch dargestellte Zahlen mit beliebigem g angeben. Eine interessante Frage ist, wie schnell man die arithmetischen Operationen ausfuhren kann. Um diese Frage sinnvoll stellen zu konnen, mu man zuerst ein Berechnungsmodell festlegen, z.B. eine Turing-Maschine oder eine Random Access Maschine (RAM). Hier gehen ich davon aus, da die ganzen Zahlen binar dargestellt sind. Unter der Rechenzeit, die ein Verfahren benotigt, verstehe ich die Anzahl der arithmetischen Operationen und Vergleiche von Bits, die innerhalb der Rechnung ausgefuhrt werden. Eine genauer beschriebenes Berechnungsmodell ndet sich in [1]. Es ist klar, da man zwei n-Bit Zahlen in Zeit O(n) addieren und subtrahieren kann. Bezeichnet man mit M (n) die minimale Zeit, die fur die Multiplikation zweier n-Bit Zahlen gebraucht wird und mit D(n) die Zeit, die man braucht, um eine Zahl von hochstens 2n Bits durch eine n-Bit Zahl zu dividieren, so gilt der folgende, in [1] bewiesene Satz.

1.4.3. Satz Es gibt positive reelle Zahlen c und c0 mit cM (n)  D(n)  c0M (n). Dies bedeutet, da Multiplikation und Division mit Rest im wesentlichen gleich schwere Probleme sind. In [1] wird auerdem folgendes bewiesen.

1.4.4. Satz M (n) = O(n log n log log n). (Schulmethode: O(n2)) Der Beweis erfolgt, indem diese Laufzeitschranke fur den Multiplikationsalgorithmus von Schonhage und Strassen gezeigt wird. Nennt man eine Funktion f : IN ! IR>0 quasilinear, wenn f (n) = O(n1+" ) fur jedes " > 0 ist, so bedeutet Satz 1.4.4, da man zwei ganze Zahlen in quasilinearer Laufzeit multiplizieren kann.

Version 6. August 1996

10

Diese Analysen geben zwar ein Gefuhl fur die Schwierigkeit der Multiplikation und Division von ganzen Zahlen. Sie beantworten aber nicht die Frage, welchen Algorithmus man in der Praxis verwenden soll. Dies kann man nur durch Bestimmung der O-Konstante und durch Experimente heraus nden. Aber auch dann hangt die Ezienz des verwendeten Verfahrens noch wesentlich von der Implementierung ab. So arbeitet Schonhage schon lange daran, zu zeigen, da sein Multiplikationsverfahren schon fur relativ kleine Zahlen ezient ist. Siehe hierzu [11]. Fur praktische Informationen und Implementierungshinweise siehe [7].

1.5 Groter gemeinsamer Teiler 1.5.1. De nition Ein gemeinsamer Teiler einer Menge M von ganzen Zahlen ist eine ganze Zahl, die alle Elemente von M teilt. Ein gemeinsamer Teiler d von M heit groter gemeinsamer Teiler von M , wenn er von allen anderen gemeinsamen Teilern von M geteilt wird und d  0 gilt. Schreibweise: d = ggT(M ). 1.5.2. Beispiel ggT(f0g) = 0, ggT(fag) = a. 1.5.3. Satz Jede Menge M von ganzen Zahlen besitzt genau einen groten gemeinsamen

Teiler. Enthalt M ein von Null verschiedenes Element, so ist der grote gemeinsame Teiler die grote naturliche Zahl, die alle Elemente von M teilt.

Beweis: Zuerst wird die Eindeutigkeit gezeigt. Seien d und d0 zwei grote gemeinsame

Teiler von M , dann ist nach De nition d ein Teiler von d0 und d0 ein Teiler von d. Also folgt aus (1.15), da d = d0, weil beide nicht negativ sind. Besteht M nur aus einem einzigen Element, so ist der Betrag dieses Elementes der grote gemeinsame Teiler von M . Jetzt wird die Existenz fur den Fall nachgewiesen, da M zwei Elemente a1 und a2 enthalt. Ohne Beschrankung der Allgemeinheit kann angenommen werden, da a2 > 0 ist. Fuhre in folgender Weise Divisionen mit Rest durch:

a1 = q1a2 + a3; 0  a3 < a2 a2 = q2a3 + a4; 0  a4 < a3 a3 = q3a4 + a5; 0  a5 < a4

usw. Die Folge der Reste ist streng monoton fallend. Nach einer endlichen Anzahl von Schritten geht also die letzte Division mit Rest auf, d.h. man hat

ak;1 = qk;1 ak + ak+1; 0 < ak+1 < ak ak = qk ak+1 + 0:

Es wird nun behauptet, da ak+1 ein groter gemeinsamer Teiler von a1 und a2 ist. Das beweist man so: Einerseits erkennt man beim Durchgang der Rekursionsgleichungen von unten nach oben, da ak+1 alle ai mit i  k + 1 teilt. Andererseits sieht man beim

Version 6. August 1996

11

Durchgang der Rekursionsgleichungen von oben nach unten, da jeder gemeinsame Teiler von a1 und a2 alle ai teilt fur 1  i  k + 1, insbesondere also ak+1 . Wenn M nur endlich viele Elemente enthalt, so beweist man die Existenz des groten gemeinsamen Teilers induktiv. Der grote gemeinsame Teiler einer unendlichen Menge M ist der kleinste unter den groten gemeinsamen Teilern 6= 0 der endlichen Teilmengen von M. Als Abkurzung fur \groter gemeinsamer Teiler" benutzt man \ggT". Sind a1; : : :; ak ganze Zahlen, so bezeichnet gcd(a1 ; : : :; ak ) den ggT von fa1; : : :; ak g.

1.5.4. Satz Der ggT von ganzen Zahlen a1; : : :; ak ist eine ganzzahlige Linearkombination dieser Zahlen, d.h. es gibt ganze Zahlen c1; : : :; ck fur die gcd(a1 ; : : :; ak ) = c1 a1 + : : :+ ck ak gilt.

Beweis: Ich verwende die Bezeichnungen aus dem Beweis von Satz 1.5.3. Dort ist

gcd(a1 ; a2) = ak+1 = ak;1 ; qk;1 ak . Hierin kann man ak ersetzen mittels ak = ak;2 ; qk;2 ak;1 . Setzt man dieses Verfahren fort, so folgt die Behauptung fur k = 2. Fur k > 2 zeigt man die Behauptung durch vollstandige Induktion.

Aus den Beweisen von Satz 1.5.3 und Satz 1.5.4 erhalt man Algorithmen zur Berechnung des ggT zweier Zahlen und zur Bestimmung der Koezienten in der Darstellung dieses ggT als ganzzahlige Linearkombination. Hier sind die Algorithmen.

1.5.5. Algorithmus Euklidischer Algorithmus

Eingabe: Ganze Zahlen a; b. Ausgabe: d = gcd(a; b) (1) d = maxfjaj; jbjg, r = minfjaj; jbjg (2) while (r 6= 0) do (3) h = r; r = d ; bd=rcr; d = h (4) od

Version 6. August 1996

12

1.5.6. Algorithmus Erweiterter Euklidischer Algorithmus

Eingabe: Ganze Zahlen a; b Ausgabe: d = gcd(a; b) und ganze Zahlen e; f mit d = ae + bf (1) (2)

if (jaj  jbj) then

(3) (4)

else

(5) (6) (7)

while (r 6= 0) do

(8) (9)

d = jaj; r = jbj, e = sign(a), e0 = 0, f = 0, f 0 = sign(b) d = jbj, r = jaj, f = sign(b), f 0 = 0, e = 0, e0 = sign(a) q0= bd=rc1 0 1 ! d r d r 0 1 B C B C 0 0 @ e e A = @ e e A 1 ;q f f0 f f0

od

Den Beweis folgender Resultate ndet man in [2].

1.5.7. Satz Seien a; b zwei ganze Zahlen mit jaj  jbj > 1. 1. Die Anzahl der Iterationen in Algorithmus 1.5.5 und Algorithmus 1.5.6 ist hochstens p log jbj= log((1 + 5)=2) + 1. 2. Die Laufzeit von Algorithmus 1.5.5 und Algorithmus 1.5.6 ist O(size(a) size(b)). 3. Fur die Koezienten e und f , die in Algorithmus 1.5.6 berechnet werden, gilt jej  jbj=(2 gcd(a; b)) und jf j  jaj=(2 gcd(a; b)). Gilt ferner gcd(a; b) = e0a + f 0b fur zwei ganze Zahlen e0 und f 0 , so folgt je0 j  e und jf 0j  f .

Auerdem wird in [1] folgender Satz bewiesen.

1.5.8. Satz Ist M (n) die Zeit, die man zur Multiplikation zweier n-Bit Zahlen benotigt,

so gibt es einen Algorithmus, der den ggT zweier n-Bit Zahlen mit Darstellung in Zeit O(M (n) log n) berechnet.

Mit diesem Satz und Satz 1.4.4 erhalt man folgendes Ergebnis.

Version 6. August 1996

13

1.5.9. Satz Der ggT zweier n-Bit Zahlen mit Darstellung kann in Zeit O(n log2n log log n) bestimmt werden.

Wendet man obige Algorithmen iteriert an, so kann man damit auch den ggT mit Darstellung von k Zahlen berechnen: ggT(a1 ; a2; a3; : : :; ak ) = ggT(d1; a3; a4; : : :; ak ); mit d1 = x1 a1 + x2 a2 = ggT(d2; a4; : : :; ak ); mit d2 = y2 d1 + y2 a3 = x1 y1 a1 + x2 y1 a2 + y2 a3 = ggT(d3; a5; : : :; ak ); mit d3 = z1 d2 + z2 a4 = x| 1 y{z1 z1} a1 + x| 2 y{z1 z1} a2 + y2 z1 a3 + z2 a4 = ::: Koezienten werden zu gro Die Koezienten dieser Darstellung sind dann aber alles andere als optimal. Besser: Man kann sogar zeigen, da das Problem, einen bezuglich der Maximumnorm minimalen Koezientenvektor zu nden, NP-vollstandig ist (siehe [6]).

1.6 Eindeutige Primfaktorzerlegung 1.6.1. Satz

1. Aus a j bc und gcd(a; b) = 1 folgt a j c.

2. Teilt eine Primzahl ein Produkt ganzer Zahlen, so teilt sie wenigstens einen Faktor.

Beweis: Nach Satz 1.5.4 ist 1 = ae + bf mit ganzen Zahlen e; f . Daher ist c = a(ce) + (bc)f . Hieraus folgt a j c.

Fur zwei Faktoren folgt die zweite Behauptung aus der ersten. Fur mehr als zwei Faktoren durch vollstandige Induktion.

1.6.2. Satz Jede naturliche Zahl a > 1 ist ein Produkt von Primzahlen. Die Zerlegung in Primfaktoren ist bis auf die Reihenfolge eindeutig. Beweis: Die Existenz der Primfaktorzerlegung von a wird durch vollstandige Induktion

gezeigt. Fur a = 2 ist die Behauptung wahr. Sei a > 2 und sei a keine Primzahl. Nach Satz 1.3.3 besitzt a einen Primfaktor p. Sei b = a=p. Dann ist 1 < b < a und nach Induktionsannahme ist b ein Produkt von Primzahlen, und das beweist die Behauptung. Seien p1p2


pr = a = q1 q2


qs zwei Primfaktorzerlegungen von a, wobei r minimal sei. Ich fuhre den Beweis durch vollstandige Induktion uber r. Ist r = 1, so mu s = 1 und q1 = p1 sein, weil Primzahlen keine nichttriviale Zerlegung besitzen. Sei r > 1. Dann ist nach Satz 1.6.1 pr ein Teiler eines der qi und damit ist pr = qi fur ein i. Ohne Beschrankung der Allgemeinheit sei pr = qs , also p1


pr;1 = q1


qs;1 . Nach Induktionsannahme sind diese Zerlegungen bis auf die Reihenfolge gleich, und das beweist die Behauptung.

Version 6. August 1996

14

Nach Satz 1.6.2 kann man fur jede von 0 verschiedene ganze Zahl a

a=

Y

p2IP

pe(p;a)

schreiben. Dies de niert also eine Abbildung

e : IP  ZZ ; f0g ! ZZ0; (p; a) 7! e(p; a):

1.6.3. U bung Man zeige, da fur ganze Zahlen a; b; a1; : : :; ak 6= 0 gilt: 1. 2. 3. 4.

Fur alle Primzahlen p gilt e(p; ab) = e(p; a) + e(p; b). a teilt b genau dann, wenn e(p; a)  e(p; b) gilt fur alle Primzahlen p. Es gilt a = b genau dann, wenn e(p; a) = e(p; b) ist fur alle Primzahlen p. Q gcd(a1; : : :; ak ) = pminfe(p;ai):1ikg . p2IP

Die Primfaktorzerlegung einer naturlichen Zahl tatsachlich zu nden, ist sehr schwer. Es ist kein polynomialer Algorithmus bekannt, der dieses Problem lost. Siehe hierzu [10]. A ndert man das Berechnungsmodell und verwendet einen sogenannten Quantencomputer, also einen Computer, der die Gesetze der Quantenmechanik ausnutzt, so kann man tatsachlich in (probabilistischer) Polynomzeit faktorisieren, siehe [12]. Es ist aber noch nicht klar, ob man einen solchen Computer wirklich bauen kann.

1.7 Kongruenzen Sei m eine naturliche Zahl.

1.7.1. De nition Zwei ganze Zahlen a und b heien kongruent modulo m, wenn m die Dierenz b ; a teilt. Man schreibt a  b mod m.

1.7.2. U bung Zeige, da genau dann a  b mod m gilt, wenn a und b denselben Rest bei der Division durch m lassen.

 1.7.3. Satz Kongruenz modulo m ist eine Aquivalenzrelation auf ZZ.

Version 6. August 1996

15

Die A quivalenzklasse von a heit Restklasse von a mod m. Ich bezeichne sie mit a Mod m. Aus Satz 1.4.1 folgt, da a Mod m genau einen Vertreter r enthalt mit 0  r < m. Dieser wird kleinster nichtnegativer Rest von a mod m genannt. Es ist auch leicht einzusehen, da es genau einen Vertreter r in a Mod m gibt mit ;m=2 < r  m=2. Das ist der absolut kleinste Rest von a mod m. Die Restklassen mod m kann man also durch einen dieser Reste eindeutig darstellen. Fur jedes a kann man beide Reste in quasilinearer Zeit ausrechnen. Daher kann man in quasilinearer Zeit entscheiden, ob fur zwei ganze Zahlen a und b die Restklassen a Mod m und b Mod m ubereinstimmen. Dies ist nicht selbstverstandlich. Es gibt A quivalenzrelationen, z.B. die A quivalenz von inde niten binaren quadratischen Formen, fur die kein polynomieller Entscheidungsalgorithmus bekannt ist.

1.7.4. Satz Kongruenz mod m ist vertraglich mit der Addition, Subtraktion und Multiplikation, d.h. aus a  a0 mod m und b  b0 mod m folgt a + b  a0 + b0 mod m, a ; b  a0 ; b0 mod m, ab  a0b0 mod m. Mit Satz 1.7.3 de niert man Addition, Subtraktion und Multiplikation von Restklassen so:

a Mod m + b Mod m = (a + b) Mod m; a Mod m ; b Mod m = (a ; b) Mod m; a Mod m
b Mod m = (ab) Mod m: Es gelten dieselben Rechengesetze wie bei ganzen Zahlen. Stellt man Restklassen durch die kleinsten nichtnegativen Reste dar, so addiert man Restklassen, indem man die Vertreter addiert und dann mod m reduziert. Entsprechend subtrahiert und multipliziert man Restklassen. Dies geht in quasilinearer Zeit. In der Praxis ist das Rechnen mit Restklassen aber erheblich zeitaufwendiger als das Rechnen mit ganzen Zahlen, weil die O-Konstante mehr als doppelt so gro ist.

1.7.5. Beispiel 3 Mod 7, 5 Mod 7.

3 + 5 = 8; 8 = 1
7 + 1 ) 3 + 5 = 1 Mod 7. In der Praxis fuhrt man evtl. nur eine Subtraktion mit 7 aus: 3 + 5 = 8; 8 ; 7 = 1 ) 3 + 5 = 1 Mod 7.

1.7.6. Beispiel Lose x2 + y2 = 1003.

Betrachte Gleichungssystem Mod 4: x2 + y 2 = 3 Mod 4. x Mod 4 0 1 2 3 2 2 x2 Mod 4 0 1 0 1 ) x + y 2 f0; 1; 2g Mod4. ) x2 + y2 = 3 Mod4 hat keine Losung und damit auch nicht x2 + y2 = 1003. Satz 1.7.3 ist sehr nutzlich bei der Rechnung mit Kongruenzen. Will man z.B. den Rest einer ganzen Zahl k X a = ai 10k;i i=1

Version 6. August 1996

16

mod 11 bestimmen, so benutzt man 10k;i  (;1)k;i mod 11 und erhalt

a

Pk

k X i=1

ai(;1)k;i mod 11:

Der Ausdruck ai (;1)k;i heit alternierende Quersumme von a. Um Teilbarkeit von a i=1 durch 11 festzustellen, braucht man nur zu prufen, ob die alternierende Quersumme von a durch 11 teilbar ist.

1.7.7. Beispiel 1213 = 3 + (;1) + 2 + (;1) = 3 Mod11 ) 116 j 1213. 121 = 1 + (;2) + 1 = 0 Mod 11 ) 11 j 121.

Division mod m ist nicht immer moglich, wie der folgende Satz zeigt.

1.7.8. Satz Genau dann gibt es eine ganze Zahl a0 mit aa0  1 mod m, falls gcd(a; m) = 1 ist.

Beweis: Ist gcd(a; m) = 1, so gibt es nach Satz 1.5.4 ganze Zahlen a0; c mit 1 = aa0 + cm also aa0  1 mod m.

Gilt aa0  1 mod m so gibt es eine ganze Zahl c mit aa0 + cm = 1. Also ist gcd(a; m) = 1.

1.7.9. De nition Gilt gcd(a; m) = 1, so heit a Mod m prime Restklasse mod m. Gilt aa0  1 mod m so schreibe ich auch a0  a;1 mod m und (a Mod m);1 = a0 Mod m. a;1 heit Inverse von a. Es gilt noch folgende Kurzungsregel.

1.7.10. Satz Ist gcd(a; m) = 1 so folgt aus ab  ac mod m, da auch b  c mod m gilt. Beweis: Wahle a0 mit a0a  1 mod m und erhalte b  a0ab  a0ac  c mod m. Um eine prime Restklasse mod m zu invertieren, mu man den ggT mit Darstellung des Vertreters mit m berechnen. Dies geht auch in quasilinearer Zeit. Division durch prime Restklassen geht also auch in quasilinearer Zeit.

1.7.11. Beispiel a = b = 2; c = 4; m = 4. ab = 0 = ac mod m. Aber b 6= c mod m.

Kapitel 2

Gruppen 2.1 Algebraische Struktur 2.1.1. De nition Es seien X ud Y Mengen. Eine Abbildung f : X  X ! X heit

innere Verknupfung auf X . Eine Abbildung g : X  Y ! X heit auere Verknupfung auf X mit Operatorenbereich Y . Ein Tupel (X; f1; : : :; fn; Y1; g1; : : :; Ym; gm) bestehend aus einer nicht leeren Menge X , inneren Verknupfungen fi auf X , 1  i  n, und aueren Verknupfungen gj auf X mit nicht leerem Operatorenbereich Yj , 1  j  m heit eine algebraische Struktur. Ist f eine innere Verknupfung auf einer Menge X , so schreibt man xfy statt f (x; y ). Zum Beispiel sind Addition und Multiplikation Verknupfungen auf der Menge der ganzen Zahlen und auch auf der Menge der Restklassen mod m fur jede naturliche Zahl m. Andere Beispiele fur innere Verknupfungen auf Mengen sind die Konkatenation auf der Menge aller Strings uber einem endlichen Alphabet und die logischen Verknupfungen _ und ^ auf der Menge f0; 1g.

2.1.2. U bung Sei m eine naturliche Zahl. Zeige, da die Multiplikation von Restklassen

eine Verknupfung auf der Menge der primen Restklassen mod m ist. Zeige auch, da die Addition von Restklassen keine Verknupfung auf dieser Menge ist.

2.1.3. Beispiel Eine auere Verknupfung auf der Menge aller Restklassen nach einem

naturlichen Modul m mit Operatorbereich IN ist die Potenzierung ZZ=mZZ  IN ! ZZ=mZZ; (x Mod m; n) 7! xn Mod m: Fur die Menge der primen Restklassen mod m kann man diese Verknupfung sogar auf den Operatorbereich ZZ fortsetzen. Innere Verknupfungen auf einer endlichen Menge X = fx1 ; : : :; xng kann man durch eine Verknupfungstafel angeben. Folgende Verknupfungstafel beschreibt z.B. die Multiplikation auf ZZ=4ZZ. 17

Version 6. August 1996

18


0 1 2 3

0 1 2 3

0 0 0 0

0 1 2 3

0 2 0 2

0 3 2 1

Aus der Symmetrie der Verknupfungstafel folgt die Kommutativitat der Verknupfung. Da 2
2 = 0, ist ZZ=4ZZ keine Gruppe.

2.1.4. De nition Seien (X; >1; : : :; >n; Y1; ?1; : : :; Ym; ?m) und

(U; _1; : : :; _n ; Y1; ^1; : : :; Ym ; ^m ) algebraische Strukturen mit gleicher Anzahl innerer und auerer Verknupfungen und gleichen Operatorbereichen. Eine Abbildung f : X ! U heit Homomorphismus der ersten Struktur in die zweite, wenn sie folgende Bedingungen erfullt: 1. f (a>i b) = f (a) _i f (b) fur alle a; b 2 X und 1  i  n. 2. f (y ?i a) = y ^i f (a) fur alle y 2 Yi , a 2 X und 1  i  m. Injektive Homomorphismen heien Monomorphismen, surjektive Homomorphismen heien Epimorphismen, bijektive Homomorphismen heien Ismorphismen. Homomorphismen einer algebraischen Struktur in sich selbst heien Endomorphismen, bijektive Endomorphismen heien Automorphismen.

2.1.5. Beispiel Sei m eine naturliche Zahl. Dann ist die Abbildung ZZ ! ZZ=mZZ; a 7! a Mod m ein Epimorphismus von (ZZ; +;
) in (ZZ=mZZ; +;
). Mit der aueren Verknupfung a^n = an liefert obige Abbildung einen Epimorphismus von (ZZ; IN;^) in (ZZ=mZZ; IN;^) und von (ZZ; +;
; IN;^) in (ZZ=mZZ; +;
; IN;^).

2.1.6. De nition Eine innere Verknupfung  : X  X ! X heit assoziativ, wenn a  (b  c) = (a  b)  c gilt fur alle a; b; c 2 X . Sie heit kommutativ, wenn a  b = b  a gilt fur alle a; b 2 X .

2.1.7. Beispiel Potenzieren als innere Verknupfung: (34)5 6= 3(4 ). 5

Subtrahieren: (a ; b) ; c 6= a ; (b ; c)8a = b; c 6= 0; a; b; c 2 ZZ.

Es soll gezeigt werden, da bei einer assoziativen Verknupfung das Ergebnis einer Verknupfung von n Elementen von der Klammerung unabhangig ist.

2.1.8. De nition Sei eine innere Verknupfung  : X X ! X und eine Folge (x1; : : :; xn) von Elementen aus X vorgegeben. Die Verknupfungen dieser Folge (bezuglich ) sind induktiv folgendermaen de niert.

Version 6. August 1996

19

1. Ist n = 1 so ist x1 die einzige Verknupfung der Folge. 2. Ist n > 1, 1  i < n, ist u eine Verknupfung von (x1; : : :; xi) und v eine Verknupfung von (xi+1; : : :; xn ), so ist u  v eine Verknupfung von (x1; : : :; xn ).

2.1.9. Satz Ist  eine assoziative Verknupfung auf der Menge X und ist f eine endliche Folge von Elementen von X , so sind alle Verknupfungen von f gleich.

Beweis: Der Beweis wird durch Induktion uber die Lange von f gefuhrt. j f j= 1: klar. f = (x1; : : :; xn ); u  v Ind:Ann: = (x1  w)  v Ass: = x1  (w  v ) ) Beh.

Die einzige Verknupfung von f = (x1; : : :; xn ) in Satz 2.1.9 wird mit n i=1

xi

bezeichnet.

2.2 Halbgruppen 2.2.1. De nition Eine Halbgruppe ist ein Paar (H; ), bestehend aus einer nichtleeren Menge H und einer assoziativen inneren Verknupfung  auf H .

2.2.2. Beispiel

1. Das Paar (IN; +) ist eine Halbgruppe. 2. Ist  ein Alphabet, so ist (; ) eine Halbgruppe, wobei  die Konkatenation von Strings bedeutet.

In einer Halbgruppe (H; ) de niert man zu jedem Element a 2 H und jeder naturlichen Zahl n die n-te Potenz , indem man a1 = a und an+1 = a  an setzt.

2.2.3. Satz Fur a 2 H und n; m 2 IN gilt an  am = an+m sowie (an)m = anm. Berechnet man an durch sukzessive Multiplikation, so braucht man dafur n ; 1 Multiplikationen in H . Man kann Satz 2.2.3 benutzen, um diese Berechnung wesentlich zu beschleunigen. Hierzu schreibt man den Exponenten n in Binardarstellung auf, d.h. als

n=

k X i=0

bi2k;i :

Version 6. August 1996

20

Nach Satz 2.2.3 gilt dann k

k

=0

bk;i =1

an = i (a2k;i ) = i (a2i ): =0

bi =1

Dies legt es nahe, i die Potenzen a2i zu berechnen fur 1  i  k und an als Produkt der entsprechenden a2 zu bestimmen. Hierbei beachte man, da

a2i = (a2i )2 +1

ist. Dies fuhrt zu folgendem Algorithmus.

2.2.4. Algorithmus Schnelle Exponentiation

Eingabe: a 2 H , n 2 IN Ausgabe: b = an (1) b = a; n = n ; 1; c = a; (2) while (n > 0) do (3) if (n  1 mod 2) then (4) b = b  c; n = n ; 1; (5) (6) n = n=2; c = c2; (7) od

2.2.5. Satz Algorithmus 2.2.4 benotigt hochstens 2(blog nc + 1) = 2blog nc + 2 Multiplikationen in H . 2.2.6. U bung Eine Variante der schnellen Exponentiation in Halbgruppen beruht auf folgender Formel

(

(g n=2)2 fur n  0 mod 2 g
(g(n;1)=2)2 fur n 6 0 mod 2 : Man gebe den entsprechenden Algorithmus an und analysiere ihn.

gn =

Exponentiation in (H; ) kann zu kryptographischen Zwecken verwendet werden. Wollen sich zwei Kommunikationspartner A und B uber eine unsichere Leitung auf einen geheimen Schlussel einigen, so einigen sie sich oentlich auf ein Element h 2 H . Dann wahlt A einen geheimen Exponenten a, bestimmt  = ha und schickt  an B. B wahlt einen geheimen Exponenten b, bestimmt = hb und schickt an A. Danach bestimmt A das Element

Version 6. August 1996

21

a = (hb )a = hab und B bestimmt das Element b = (ha)b = hab. Beide haben also dasselbe Element hab , das sie als Schlussel verwenden. Man beachte, da hier mehrfach die Potenzgesetze aus Satz 2.2.3 verwendet wurden. Ein Lauscher kennt H , h, , . Hieraus hab zu berechnen, bezeichnet man als das Die-Hellman-Problem in H nach den Er ndern dieses Verfahrens Die und Hellman (siehe [5]). Der Lauscher konnte hab ermitteln, wenn er die Exponenten a und b bestimmen konnte. Der Exponent a heit diskreter Logarithmus von  zur Basis h. Es ist klar, da das Die-Hellman-Problem hochstens so schwer ist, wie das Problem, in H diskrete Logarithmen zu berechnen. Die Umkehrung ist nicht bekannt und gehort zu den wichtigen oenen Problemen der Kryptoanalyse. In der Praxis wird vor allem die multiplikative Halbgruppe der primen Restklassen nach einem groen Primzahlmodul p verwendet. Hat p mehr als 200 Dezimalstellen und p ; 1 nicht zu kleine Faktoren, so gelten obige Probleme zur Zeit als unlosbar.

2.3 Direkte Produkte Es sei I eine nicht leere Menge, die hier als Indexmenge gebraucht wird. Es sei f(H; >)g eine Familie von Halbgruppen. Auf dem mengentheoretischen direkten Produkt

Y

2I

H = ff jf : I ! [2I H mit f () 2 Hg

de niert man komponentenweise eine innere Verknupfung

>:

Y

2I

H 

Y

2I

H !

Y

2I

H

durch

(f >g )() = f ()> g (): Q Diese Verknupfung ist assoziativ. Also ist ( 2I H ; >) eine Halbgruppe. Sie heit direktes Produkt der Halbgruppen f(H; >)g. Analog werden direkte Produkte beliebiger algebraischer Strukturen de niert.

2.4 Faktorhalbgruppen In diesem Abschnitt sei (H; ) eine Halbgruppe und R eine A quivalenzrelation auf H .  2.4.1. De nition Die Aquivalenzrelation R heit mit der Verknupfung  linksvertraglich

bzw. rechtsvertraglich, wenn fur alle (x; y ) 2 R und alle a 2 H auch (a  x; a  y ) bzw. (x  a; y  a) in R liegt. Die Relation R heit vertraglich mit , wenn sie linksvertraglich und rechtsvertraglich mit  ist.

2.4.2. Beispiel Sei  = f0; 1g und  die Konkatenation auf . Wir betrachten die

Halbgruppe (; ). Wir nennen zwei Strings in  aquivalent, wenn sie gleich lang sind. Dies ist eine A quivalenzrelation, die mit  vertraglich ist.

Version 6. August 1996

22

2.4.3. U bung Betrachte die Halbgruppe der (ZZnn ;
). Wir nennen zwei Matrizen A; B 2

ZZnn aquivalent, wenn es eine Matrix U 2 ZZnn gibt mit det U = 1 und A = UB . Zeige, da dies eine A quivalenzrelation ist. Untersuche, ob die A quivalenzrelation mit
vertraglich ist.

2.4.4. Satz Genau dann ist  mit R vertraglich, wenn mit (x; y); (u; v) 2 R auch (x  u; y  v) zu R gehort.

Beweis: "(\: Sind die angegebenen Bedingungen erfullt, so ist R mit  vertraglich, weil man (x; y) = (a; a) bzw. (u; v) = (a; a) setzen kann. R mit  vertraglich und (x; y ); (u; v) 2 R. Dann gilt (x  u; y  u) 2 R und "(y)\:u; ySei  v) 2 R. Daher folgt aus der Transitivitat von R, da auch (x  u; y  v) zu R gehort. Die A quivalenzklasse von a 2 H wird mit [a]R oder kurz [a] bezeichnet. Die Menge aller A quivalenzklassen wird H=R geschrieben.

2.4.5. Satz Sei R vertraglich mit . De niert man [a]  [b] = [a  b] fur a; b 2 H , so ist (H=R; ) eine Halbgruppe.

Die in Satz 2.4.5 konstruierte Halbgruppe heit Faktorhalbgruppe oder Restklassenhalbgruppe von R nach H .

2.5 Neutrale Elemente Wieder sei (H; ) eine Halbgruppe.

2.5.1. De nition Ein Element e 2 H heit rechtsneutrales bzw. linksneutrales Element

der Halbgruppe, wenn a  e = a bzw. e  a = a gilt fur alle a 2 H . Ist e zugleich rechtsneutrales und linksneutrales Element der Halbgruppe, so heit e neutrales Element der Halbgruppe.

2.5.2. Beispiel Betrachte die Menge H aller 2  2-Matrizen mit ganzzahligen Eintragen,

in denen beide Eintrage in der zweiten Spalte 0 sind. Zusammen mit der Matrixmultipliaktion ist das eine Halbgruppe. Diese Halbgruppe besitzt kein linksneutrales Element und das rechtsneutrale Element ! 1 0 : 0 0

2.5.3. Satz Ist e ein linksneutrales und f ein rechtsneutrales Element der Halbgruppe, so

ist e = f . Insbesondere besitzen Halbgruppen hochstens ein neutrales Element.

Beweis: Es gilt e = e  f = f .

Version 6. August 1996

23

2.6 Invertierbare Elemente Wieder (H; ) eine Halbgruppe mit neutralem Element e.

2.6.1. De nition Ein Element a 2 H heit linksinvertierbar bzw. rechtsinvertierbar in

der Halbgruppe, wenn es b 2 H gibt mit b  a = e bzw. a  b = e. Ein links- und rechtsinvertierbares Element heit invertierbar.

2.6.2. Satz Ist a 2 H invertierbar mit Linksinversem b und Rechtsinversem b0, dann gilt b = b0 .

Beweis: b = b  e = b  (a  b0) = (b  a)  b0 = b0. Die Menge der invertierbaren Elemente in H wird mit H  bezeichnet. Ihre Elemente heien Einheiten von H . Man beachte, da die De nition von H  von der Verknupfung  abhangt.

2.6.3. Beispiel Betrachte die Halbgruppe (ZZ;
). Dann ist ZZ = f1g. Betrachte p die p

Halbgruppe (fx + y 5 : x; y 2 ZZg;
). In pdieser Halbgruppe ist z.B.  = (1 + 5)=2 invertierbar mit dem Inversen 0 = (;1 + 5)=2. Auerdem sind alle Potenzen von  und 0 invertierbar. Andere invertierbare Elemente gibt es in dieser Halbgruppe nicht.

2.7 Gruppen 2.7.1. De nition Eine Halbgruppe (H;
) heit Gruppe, wenn sie ein linksneutrales Element e besitzt und wenn es fur alle a 2 H ein b 2 H gibt mit b
a = e.

2.7.2. Satz Gilt a2 = a fur ein Element a einer Gruppe (G;
) mit linksneutralem Element

e, dann ist a = e.

Beweis: Sei b 2 G mit ba = e. Dann gilt a = ea = (ba)a = b(a2) = ba = e. 2.7.3. Satz Eine Halbgruppe (G;
) ist genau dann eine Gruppe, wenn sie genau ein neutrales Element enthalt und alle Elemente von G invertierbar sind.

Beweis: Wir mussen nur zeigen, da Gruppen die obigen Eigenschaften haben. Sei (G;
) eine Gruppe mit linksneutralem Element e. Sei a; b 2 G mit ba = e. Dann gilt (ab)(ab) = a(ba)b = aeb = ab. Also ist ab = e nach Satz 2.7.2. Weiter gilt a = ea = (ab)a = a(ba) = ae. Also ist e auch rechtsneutrales Element. Aus Satz 2.5.3 folgt, da e das eindeutig bestimmte neutrale Element von G ist.

Version 6. August 1996

24

Das Inverse eines Elementes a einer Gruppe G bezeichnet man mit a;1 .

2.7.4. Satz Ist (H; ) eine Halbgruppe mit neutralem Element e, so ist (H ; ) eine Grup-

pe.

Sei in Zukunft (G;
) eine Gruppe mit neutralem Element e.

2.7.5. Satz Fur a; a1; : : :; an 2 G gelten folgende Rechengesetze. 1. (a;1 );1 = a. 2. (a1a2


an );1 = a;n 1


a;1 1 . 3. (a;1 )m = (am );1 .

Setzt man a0 = e und a;n = (a;1 )n , so folgen aus Satz 2.7.5 die ublichen Potenzgesetze.

2.7.6. Satz Eine Halbgruppe (H;
) ist genau dann eine Gruppe, wenn es zu je zwei Elementen a; b Elemente x; y gibt mit ax = b und ya = b.

Die folgenden Rechengesetze werden als Kurzungsregeln bezeichnet.

2.7.7. Satz Fur alle a; b; c 2 G folgt aus ac = bc, da auch a = b gilt und aus ca = cb, da auch a = b gilt.

Ist G endlich, so heit die Elementanzahl von G auch Ordnung von G. Ist
kommutativ, so heit die Gruppe G kommutativ oder abelsch .

2.8 Beispiele von Gruppen Bekannt sind schon folgende abelsche Gruppen: (ZZ; +), (Q ; +), (Q ; f0g;
), (ZZ=mZZ; +), ((ZZ=mZZ) ;
) fur m 2 IN. Letztere Gruppe heit prime Restklassengruppe mod m. Die Menge der Permutationen S (X ) einer nicht leeren Menge X ist zusammen mit der Hintereinanderausfuhrung eine Gruppe. Sie heit symmetrische Gruppe von X . Die symmetrische Gruppe von f1; : : :; ng bezeichnet man auch als Sn und nennt sie symmetrische Gruppe der Stufe n.

2.8.1. Satz Es gilt jSnj = n!.

Version 6. August 1996

25

Unter einer Bewegung des IRn versteht man eine Permutation des IRn , die die Abstande zwischen zwei Punkten unverandert lat. Die Symmetrien einer Teilmenge F des IRn sind die Bewegungen f des IRn , die F in sich selbst abbilden, d.h. fur die f (F ) = F gilt. Die Symmetrien von F bilden zusammen mit der Hintereinanderausfuhrung eine Gruppe, die Symmetriegruppe von F . Betrachte als Beispiel fur n=2 dieses Quadrat. y 1

2

x 4

Elemente seiner Symmetriegruppe sind Spiegelungen und Drehungen um   90,  2 ZZ. Einer Spiegelung an der X-Achse entspricht z.B. die Permutation:

!

1 2 3 4 : 4 3 2 1

3

Das heit die Symmetriegruppe dieses Quadrates besteht aus den acht Elementen

(

!

!

!

!

!

!

!

!)

1 2 3 4 ; 1 2 3 4 ; 1 2 3 4 ; 1 2 3 4 ; 1 2 3 4 2 3 4 1 2 1 4 3 3 4 1 2 1 2 3 4 ; 1 2 3 4 ; 1 2 3 4 ; 1 2 3 4 1 4 3 2 4 1 2 3 3 2 1 4 4 3 2 1

2.9 Gruppentafeln Wir sind daran interessiert, alle Gruppen einer festen endlichen Ordnung zu nden. Dies ist so noch keine vernunftige Aufgabe, weil die Elemente beliebige Namen haben konnen. Z.B. ist (feg;
) eine Gruppe, wenn man einfach e
e = e setzt. Dies ist eine Gruppe der Ordnung 1. Benennt man e um, so erhalt man eine andere Gruppe der Ordnung 1. Diese ist aber isomorph zur ersten. Isomorphie von Gruppen ist eine A quivalenzrelation. Die A quivalenzklassen heien Isomorphieklassen von Gruppen. Zwei endliche Gruppen sind genau dann isomorph, wenn sie nach Umbenennung der Elemente dieselbe Verknupfungstafel haben.

2.9.1. Beispiel ((ZZ=pZZ);
) = (ZZ=(p ; 1)ZZ; +).

Da (ZZ=4ZZ) = h2i = h3i, liefert die Abbildung 2 7! 1 bzw. 3 7! 1 obigen Isomorphismus. Die Verknupfungstafel einer Gruppe heit Gruppentafel . Es kann also nur endlich viele Isomorphieklassen von Gruppen einer festen endlichen Ordnung geben. Die Aufgabe lautet nun, fur jede dieser Klassen einen Vertreter zu nden. Dies kann man machen, indem man alle moglichen Gruppentafeln angibt.

Version 6. August 1996

26

Aus der Kurzungsregel folgt, da die Zeilen und Spalten einer Gruppentafel Permutationen der Gruppenelemente sind. In der Zeile und Spalte des neutralen Elementes stehen die Gruppenelemente in der Originalreihenfolge. Sind diese beiden Regeln erfullt, so ist die Existenz von neutralem Element und der inversen Elemente gesichert und man mu noch die Assoziativitat nachprufen. Diese spiegelt sich in der Gruppentafel nicht unmittelbar wieder. Dagegen ist die Gruppe genau dann kommutativ, wenn ihre Gruppentafel symmetrisch ist bezuglich der Diagonalen von links oben nach rechts unten. Auf diese Weise werden jetzt die endlichen Gruppen der Ordnung  4 klassi ziert. Es ist klar, da es genau eine Gruppe der Ordung 1 gibt: (feg;
). Die einzig mogliche Gruppentafel fur eine Gruppe der Ordnung 2 ist

 e a e e a oder vereinfacht: ae ae a a e Diese Gruppe ist isomorph zu ZZ=2ZZ. Sie ist abelsch. Die einzig mogliche Gruppentafel fur eine Gruppe der Ordnung 3 ist

e a b a b e b e a Diese Gruppe ist isomorph zu ZZ=3ZZ. Sie ist abelsch. Fur Gruppen der Ordnung 4 gibt es genau zwei mogliche Gruppentafeln:

e a b c a e c b b c e a c b a e Diese Gruppe ist isomorph zu ZZ=2ZZ  ZZ=2ZZ und heit Klein'sche Vierergruppe. e a b c

a b c e

b c e a

c e a e  a c = a b e b c b

b e c a

c b a e

Die zweite Gruppentafel ergibt sich aus der ersten durch Vertauschen von b und c.

2.9.2. U bung Man entwickele einen Algorithmus, der nach obigem Vorbild alle endlichen Gruppen einer festen Ordnung n klassi ziert und schatze seine Komplexitat ab.

Version 6. August 1996

27

2.10 Zyklische Gruppen und Elementordnung Sei (G;
) eine Gruppe mit neutralem Element e.

2.10.1. Satz Fur alle a 2 G ist (fan : n 2 ZZg;
) eine Gruppe. 2.10.2. De nition

1. Fur a 2 G heit hai = fan : n 2 ZZg die von a erzeugte Untergruppe. Die Ordnung von a ist die Ordnung von hai. Sie wird mit ordG a bezeichnet.

2. G heit zyklisch, falls G = hai ist fur ein a 2 G. a heit Erzeuger von G.

2.10.3. Beispiel (ZZ=nZZ; +) ist zyklisch mit Erzeuger 1 und ;1 Mod n. ZZ=6ZZ : 2 +2 ! 4 +2 ! 6 = 0 ) 2 kein Erzeuger von ZZ=6ZZ.

2.10.4. Satz Sei a 2 G. 1. Gibt es eine naturliche Zahl k mit ak = e, so ist ordG a = minfk 2 IN : ak = eg und fur n; m 2 ZZ gilt an = am genau dann, wenn n  m mod ordG a. 2. Ist ordG a endlich und R ein volles Restsystem mod ordG a so gilt hai = far : r 2 Rg. 3. Gilt ak 6= e fur alle naturlichen Zahlen k, dann ist a von unendlicher Ordnung und fur n; m 2 ZZ gilt an = am genau dann, wenn n = m ist.

Beweis: Sei x = minfk : ak = eg und n; m 2 IN. Schreibe n ; m = qx + r mit q; r 2 ZZ, 0  r < x. Dann gilt an = am genau dann, wenn e = an;m = aqx+r = ar . Wegen der Minimalitat von x ist dies gleichbedeutend mit r = 0. Die Anzahl der verschiedenen Potenzen von a ist also gleich der Anzahl der Restklassen mod x. Hieraus folgen alle drei Behauptungen.

2.10.5. Satz a Mod n ist Erzeuger von (ZZ=nZZ; +) , ggT(a; n) = 1. Beweis: a Mod n erzeugt (ZZ=nZZ; +) , 8b 2 ZZ 9x 2 ZZ : ax  b mod n , 9x 2 ZZ : ax  1 mod n , ggT(a; n) = 1.

2.10.6. Korollar Fur a 2 G, n 2 ZZ gilt genau dann an = e, wenn n ein Vielfaches der Ordnung von a ist.

Version 6. August 1996

28

2.10.7. Satz Ist G eine zyklische Gruppe der Ordnung n 2 IN, so ist G = ZZ=nZZ. Genauer gilt:

Ist G = hai, so ist die Abbildung

. G ;! ZZ nZZ; aj 7;! j Mod n

ein Gruppenisomorphismus.

Beweis: Wohlde niertheit (d.h. ai = aj ) i  j mod n) und Injektivitat (d.h. i 

j mod n ) ai = aj ) der angegebenen Abbildung folgen mit Satz 2.10.4. Da G und ZZ=nZZ beide n Elemente haben, folgt aus Injektivitat auch Surjektivitat, also ist die angegebene

Abbildung bijektiv. Die Potenzgesetze implizieren, da die Abbildung auch ein Homomorphismus ist.

2.10.8. Beispiel G = ((ZZ=7ZZ);
) e 0 1 2 3 4 5 6 2e 1 2 4 1 2 4 1 3e 1 3 2 6 4 5 1

) 3 ist Erzeuger von G, (ZZ=7ZZ;
) ! (ZZ=6ZZ; +); 3i 7! i ist Isomorphismus. 3i 1 2 3 4 5 6 i 0 2 1 4 5 3

2.10.9. Satz

1. Fur a 2 G und m 2 ZZ gilt ordG am = ordG a= gcd(ordG a; m).

2. Fur a; b 2 G folgt aus ab = ba und gcd(ordG a; ordG b) = 1, da ordG (ab) = (ordG a)(ordG b) ist.

Beweis: Sei  = ordG a. Dann gilt (am)n = e genau dann, wenn jnm. Dies ist gleichbe-

deutend damit, da = gcd(; m) ein Teiler von n ist. Die kleinste Zahl n, die das erfullt ist = gcd(; m). Diese ist nach Satz 2.10.4 die Ordnung von am . Die zweite Behauptung wird als U bung bewiesen.

2.10.10. Satz

1. Eine unendliche zyklische Gruppe hat genau zwei Erzeuger. Ist a ein Erzeuger, so ist a;1 der andere.

2. Eine endliche zyklische Gruppe hat genau '(jGj) Erzeuger. Ist a ein Erzeuger, so ist fam : gcd(jGj; m) = 1g die Menge aller Erzeuger. Dabei ist '(x)Qdie Eulersche '{Funktion, d.h. '(x) = jfy 2 INjy < x und ggT(y; x) = 1gj = x
(1 ; p1 ), z.B. xjp '(p) = p ; 1.

Version 6. August 1996

29

Beweis: Sei a ein Erzeuger der zyklischen Gruppe G. Sei G unendlich. Sei m 2 ZZ und am ein anderer Erzeuger von G. Dann mu es fur alle n 2 ZZ ein x 2 ZZ geben mit an = axm. Aus Satz 2.10.4 folgt, da n = xm losbar sein mu fur alle n 2 IN. Damit ist m = 1. Sei G endlich. Ein Element am ist genau dann ein Erzeuger von G, wenn ordG am = ordG a. Dies ist nach Satz 2.10.9 gleichbedeutend damit, da gcd(jGj; m) = 1 ist. Aus Satz 2.10.4 folgt, da die Anzahl der Erzeuger gerade '(jGj) ist. Ist m eine naturliche Zahl und ist b 2 G, so nennt man eine Losung x der Gleichung xm = b eine m-te Wurzel von b.

2.10.11. Satz Sei m eine naturliche Zahl. Ein Element b einer endlichen zyklischen Gruppe hat genau dann eine m-te Wurzel, wenn bjGj= gcd(m;jGj) = 1 ist. Die Anzahl der m-ten Wurzeln ist dann gcd(m; jGj). Beweis: Sei a ein Erzeuger von G, a = b. Der Ansatz x = a fuhrt zu der Gleichung

am = a , also nach Satz 2.10.4 zu der Kongruenz m  mod jGj. Diese Kongruenz ist genau dann losbar, wenn gcd(m; jGj) j , d.h. gcd(m; jGj) j gcd(jGj; ), d.h. ordG b = jGj= gcd(jGj; ) teilt jGj= gcd(jGj; m), d.h. bjGj= gcd(jGj;m) = e. Die Anzahl der mod jGj verschiedenen Losungen der Kongruenz ist die Anzahl der m-ten Wurzeln.

2.10.12. Satz Eine endliche Gruppe G ist genau dann zyklisch, wenn sie abelsch ist und e hochstens n verschiedene n-te Wurzeln hat fur alle naturlichen Zahlen n < jGj.

Beweis: Endliche zyklische Gruppen haben nach Satz 2.10.11 obige Eigenschaften. Habe umgekehrt die endliche Gruppe G obige Eigenschaften. Wir zeigen die Existenz eines Elementes der Ordnung jGj. Sei a ein Element maximaler Ordnung n in G. Sei b 2 G ein Element der Ordnung m. Dann ist m ein Teiler von n. Andernfalls gibt es einen Primteiler p von m, der nicht in n aufgeht. Die Ordnung von c = bm=pe p;m ist e(p; m) nach Satz 2.10.9. Die Ordnung von ac ist npe(p;m) ebenfalls nach Satz 2.10.9. Dies aber widerspricht der Maximalitat von n. Damit gilt bn = 1 fur alle b 2 G. Nach Voraussetzung kann es aber hochstens n viele solche Elemente in G geben. Damit ist n = jGj. (

)

2.11 Berechnung der Elementordnung Sei (G;
) eine Gruppe. Als elementare Operationen in G bezeichnen wir 1. die Entscheidung, ob zwei Elemente in G gleich sind, 2. die Berechnung des Produkts zweier Gruppenelemente,

Version 6. August 1996

30

3. Die Berechnung des Inversen eines Gruppenelementes. Ist G endlich, so besteht eine einfache Aufgabe darin, die Ordnung eines Elementes g zu berechnen. Dies kann man machen, indem man sukzessive die Potenzen g; g 2; : : : berechnet, bis der erste Exponent x gefunden ist mit g x = 1. Hierzu sind ordG g viele Multiplikationen und Vergleiche in G notig. Auerdem mussen konstant viele Gruppenelemente gespeichert werden. Man kann dieses Verfahren aber auf Kosten des Speicherplatzes beschleunigen. Hierzu benutzt man eine Methode, um die naturlichen Zahlen aufzuzahlen, die auf folgender Aussage beruht.

2.11.1. Satz Sei v eine gerade naturliche Zahl. 1. Die Menge der naturlichen Zahlen ist die Menge aller Zahlen x = 2k vq + r mit k 2 IN0, 1  r  2k v, b4k;1 cv2  2k qv < 4k v2 . 2. Die obige Darstellung der naturlichen Zahlen ist eindeutig, d.h. zwei so dargestellte Zahlen sind genau dann gleich, wenn k; q; r ubereinstimmen.

Beweis: Sei v 2 2IN fest. Wir zeigen zuerst, da jede naturliche Zahl x in der obigen Weise dargestellt werden kann. Wahle hierzu k so, da b4k;1 cv 2 < x  4k v 2. Schreibe dann x = 2k vq + r mit 1  r  2k v . Dann ist b4k;1 cv 2 ; 2k v < 2k vq  4k v 2 ; 1. Daraus folgt, da 2k vq < 4k v 2 ist. Auerdem erhalt man ;v < vq , also 0  vq fur k = 0. Fur k  1 gilt 4k;1v 2 ; 2k v < 2k vq, also 2k;1(v=2) ; 1 < q. Weil v gerade ist, folgt daraus 2k;1 (v=2)  q , also 4k;1 v 2  2k vq . Nun zeigen wir die Eindeutigkeit der Darstellung. Sei x in der beschriebenen Weise dargestellt. Dann gilt b4k;1 cv 2  2k vq < 4k v 2 . Daraus folgt, da q < 2k v , also q  2k v ; 1, also x = 2k vq + r < 2k v (2k v ; 1) + 2k v = 4k v 2. Fur k = 0 folgt auerdem x  1 und fur k > 0 hat man x  4k;1v2 . Die Ordnung x wird in der Darstellung x = y + r bestimmt, wobei y = 2k vq und q; r in den in Satz 2.11.1 angegebenen Schranken liegen. Der Parameter k durchlauft die Werte 0; 1; 2; : : : bis die Elementordnung gefunden ist. Zuerst wird die Menge R = f(g ;r ; r) : 1  r  2k v g vorberechnet. Diese Menge hangt naturlich von k ab und mu fur jedes neue k vergroert werden. Dann wird fur alle zulassigen y getestet, ob g y+r = 1 ist fur ein zulassiges r. Dies geschieht, indem gepruft wird, ob (g y ; r) in R vorkommt fur ein r. Sobald ein passendes Paar gefunden ist, istpdie Elementordnung x = y + r gefunden. Der Vorteil dieses Vorgehens ist, da man nur O( x) viele Multiplikationen in G braucht, um die Ordnung zu nden. Auerdem kann man in vielen Gruppen die Elemente sortieren. Dies erlaubt es, die Paare (g y ; r) nach der ersten Komponente sortiert abzuspeichern und den Test, ob (g y ; r) fur ein r zu p R gehort, mittels binarer Suche durchzufuhren. Die Ordnung x von g kann dann mittels p O( x) elementaren Operationen in G gefunden werden. Dafur mu man aber auch x viele Gruppenelemente speichern. Die Zeitersparnis geht also auf Kosten des verbrauchten Speicherplatzes. Hier ist die formale Version des Verfahrens.

Version 6. August 1996

31

2.11.2. Algorithmus Berechnung der Elementordnung

Eingabe: g 2 G, v 2 2IN Ausgabe: x = ordG g (1) x = 0; u = v ; s = 1; h = g ;1; a = 1; R = ;; (2) y = 0; b = 1; c = g v ; (3) if (g = 1) then (4) x = 1 (5) else (6) while (x = 0) do (7) for (r = s; s + 1; : : :; u) do (8) a = ah; R = R [ f(a; r)g (9) od (10) while (x = 0 and y < u2) do (11) if (there is a smallest r with (b; r) 2 R) then (12) x =y+r (13) else (14) y = y + u; b = bc (15) (16) od (17) s = u + 1; u = 2u; c = c2 (18) od (19)

2.11.3. Satz Algorithmus 2.11.2 benotigt O(pordG g) Multiplikationen und Speicherplatz

furp O( ordG g) Gruppenelemente.

Der beschriebene Algorithmus beruht auf einer Idee von D. Shanks [13]. Ich weise darauf hin, da man die Berechnung der Elementordnung noch wesentlich beschleunigen kann, wenn man die Gruppenordnung kennt. Dies wird spater noch diskutiert. Im ubrigen ist der vorgestellte Algorithmus der schnellste, der fur beliebige Gruppen bekannt ist.

2.12 Berechnung diskreter Logarithmen Die Ideen des vorigen Abschnitts konnen auch angewendet werden, um diskrete Logarithmen in beliebigen Gruppen zu berechnen. Sei (G;
) eine endliche Gruppe und seien g; d Gruppenelemente. Es soll entschieden werden, ob d zu der von g erzeugten Untergruppe gehort und wenn ja, soll z = logg d bestimmt werden. Hierzu beachte man zuerst, da im

Version 6. August 1996

32

Fall der Existenz des diskreten Logarithmus z < ordG g gilt. Wie in Algorithmus 2.11.2 wird die Ordnung von g in G bestimmt, d.h. es wird versucht, Zahlen y und r zu nden mit g y+r = 1. Fur jedes y wird aber vorher getestet, ob nicht vielleicht g y+r = d, d.h. d;1 g y = g r, d.h. (d;1gy ; r) 2 R fur ein r. Dann ist namlich der diskrete Logarithmus von d zur Basis g gefunden. Sobald aber die Ordnung von g bestimmt ist, kann es keinen diskreten Logarithmus von d zur Basis g mehr geben, weil der ja kleiner als die Ordnung sein mute. Damit ergibt sich folgender Algorithmus.

2.12.1. Algorithmus DL-Berechnung

Eingabe: g; d 2 G, v 2 2IN Ausgabe: x = ordG g oder z = logg d (1) x = 0 z = 0; ; u = v ; s = 1; h = g ;1 ; a = 1; R = ;; (2) y = 0; b = 1; c = g v ; e = d;1 (3) while (x = 0 and z = 0) do (4) for (r = s; s + 1 : : :; u) do (5) a = ah; R = R [ f(a; r)g (6) od (7) while (x = 0 and z = 0 and y < u2 ) do (8) if ((eb; r) 2 R for some r) then (9) z = y+r (10) else (11) if ((b; r) 2 R for some r) then (12) x=y+r (13) (14) else (15) y = y + u; b = bc (16) (17) od (18) s = u + 1; u = 2u; c = c2 (19) od

q

2.12.2. Satz Gilt d p2 hgi so benotigt Algorithmus 2.12.1 O( logg d) Multiplikationen und

benotigt Algorithmus 2.12.1 Speicherplatz fur O( ordG g) Gruppenelemente. Andernfalls p p O( ordG g) Multiplikationen und Speicherplatz fur O( ordG g) Gruppenelemente.

2.13 Untergruppen Sei (G;
) eine Gruppe.

Version 6. August 1996

33

2.13.1. De nition Eine Teilmenge U von G heit Untergruppe von G, wenn U bezuglich der in G de nierten Verknupfung eine Gruppe ist.

2.13.2. De nition Seien K; L nicht leere Teilmengen von G. 1. Das Komplexprodukt von K und L ist KL = fkl : k 2 K; l 2 Lg. 2. Das Komplexinverse von K ist K ;1 = fk;1 : k 2 K g. 3. Fur a 2 G setzt man auerdem aK = fagK und Ka = K fag.

2.13.3. Satz Sei U eine nicht leere Teilmenge von G. 1. Genau dann ist U eine Untergruppe von G, wenn UU ;1  U ist. 2. Ist U endlich, so ist U genau dann eine Untergruppe von G, wenn UU  U ist.

Beweis: [8] Satz 2.4.7. 2.13.4. Satz Der Durchschnitt beliebig vieler Untergruppen von G ist wieder eine Unter-

gruppe von G.

2.14 Gruppenhomomorphismen Es seien G; H Gruppen. Sei ' : G ! H ein Gruppenhomomorphismus, e das neutrale Element von G und e0 das neutrale Element von H .

2.14.1. Satz

1. '(e) ist das neutrale Element von H , da '(e) = '(e
e) = '(e)
'(e).

2. '(an ) = '(a)n fur alle a 2 G, n 2 ZZ.

Man setzt

Bild' = f'(x) : x 2 Gg Kern' = fx 2 G : '(x) = e0 g

2.14.2. Beispiel ' : (ZZ; +) ! (ZZ=mZZ; +); a 7! a Mod m Bild' = ZZ=mZZ; Kern' = mZZ:

Version 6. August 1996

2.14.3. Satz

34

1. Das Bild von ' ist eine Untergruppe von H .

2. Der Kern von ' ist eine Untergruppe von G.

2.14.4. Satz Der Homomorphismus ' ist genau dann injektiv, wenn Kern ' = feg ist. Beweis: ")\: klar.

9a 6= b : '(a) = '(b). ")('\:(a
Annahme: ;1 ) = '(a)
'(b;1) = e0. Widerspruch zu Kern' = feg ! b | {z } 6=e

Die Automorphismen von G bilden eine Gruppe, die sogenannte Automorphismengruppe von G. Ist x 2 G so ist 'x : G ! G; a 7! x;1 ax ein Automorphismus von G. Solche Automorphismen heien innere Automorphismen von G. Zwei Elemente a; b 2 G heien konjugiert , wenn b = x;1ax ist fur ein x 2 G. Zwei Untergruppen U; V von G heien konjugiert , wenn V = x;1 Ux ist fur ein x 2 G.

2.14.5. Satz Jede Gruppe G ist isomorph zu einer Untergruppe der Permutationsgruppe S (G).

Beweis: Betrachte die Abb. : G ;! G; g 7;! (G ! G; h 7! gh) = L(g), Bild =

L(G). Man zeigt, da L(G) = fL(g ) : g 2 Gg eine Untergruppe von S (G) ist und da die Abbildung L : G ! L(G); g 7! L(g ) ein Gruppenisomorphismus ist: Homomorphismus: (g
g 0)
h = g
(g 0
h) (Assoziativitat in G). Injektivitat: Sei L(g ) = L(g 0), d.h. 8h 2 G : gh = g 0h =h=)e g = g 0. Es folgt, da jede endliche Gruppe isomorph ist zu einer Untergruppe der Sn .

2.14.6. Beispiel (ZZ=6ZZ; +) : 0 7;! 1 7;! .. . 5 7;! ((ZZ=7ZZ);
) : 1 7;! 2 7;!

!

1 1 1 2

2 2 2 3

3 3 3 4

4 4 4 5

5 5 5 6

6 6 ! 6 1

1 6 1 1 1 2

2 1 2 2 2 4

3 2 3 3 3 6

4 3 4 4 4 1

5 4 5 5 5 3

6 5 ! 6 6 ! 6 5

!

Version 6. August 1996 3 7;! .. .

1 2 3 4 5 6 3 6 2 5 1 4

!

35

2.15 Der Satz von Lagrange Sei G eine Gruppe und U eine Untergruppe von G.

2.15.1. De nition Die Relation RU wird de niert durch RU = f(x; y) 2 G  G : xy;1 2 U g. RU heit auch Rechtskongruenz.

2.15.2. Beispiel G = (ZZ; +), U = 6ZZ, RU = f(x; y) 2 G  G : x ; y 2 6ZZ , x  y mod 6g

 2.15.3. Satz Die Relation RU ist eine mit der Verknupfung in G rechtsvertragliche Aqui-

valenzrelation.

Beweis: Re exivitat: xx;1 = e 2 U . Symmetrie: (x; y ) 2 RU , xy ;1 2 U Untergr. () (xy;1);1 = yx;1 2 U Transitivitat: xy ;1 2 U , yz ;1 2 U ) xy ;1 yz ;1 = xz ;1 2 U . Die A quivalenzklasse von x 2 G ist Ux. Begrundung: (yx; y 0x) 2 RU , da (yx)(y 0x);1 = yxx;1 y 0;1 = yy0;1 2 U und wenn (x; y ) 2 RU , dann ist xy;1 2 U und y = (yx;1)x = (xy ;1 );1 x 2 Ux. Sie heit Rechtsnebenklasse von U in G.

2.15.4. Beispiel G =9 (ZZ; +), U = 6ZZ 6ZZ + 0 = 6ZZ > 6ZZ + 1 6ZZ + 2 6ZZ + 3 6ZZ + 4 6ZZ + 5

> > > = alle Rechtsnebenklassen von 6ZZ in ZZ. > > > > ;

Entsprechend de niert man LU und die Linksnebenklassen von U .

2.15.5. Satz

1. Die Gruppe G ist disjunkte Vereinigung der Rechtsnebenklassen bzw. Linksnebenklassen von U in G. 2. Alle Rechtsnebenklassen bzw. Linksnebenklassen haben die gleiche Machtigkeit wie U.

Version 6. August 1996

36

2.15.6. De nition Die Anzahl der Rechtsnebenklassen von U in G heit Index von U in G und wird mit (G : U ) bezeichnet.

2.15.7. Satz (Lagrange) Die Anzahl der Rechtsnebenklassen von U in G ist gleich der Anzahl der Linksnebenklassen von U in G und es gilt jGj = (G : U )jU j.

2.15.8. Satz Ist G endlich, so folgt ajGj = 1 fur alle a 2 G. Beweis: ordG a = jhaij = minfx 2 IN : ax = 1g teilt jGj Satz=)2:15:7 ajGj = (aordG a)(G:hai) = 1.

2.15.9. U bung Satz von Fermat, Fermattest, Pseudoprimzahl. 2.15.10. Satz Jede Gruppe von Primzahlordnung ist zyklisch. 2.15.11. Satz Ist G zyklisch und ist a ein Erzeuger von G, so ist hadi fur alle Teiler d

von jGj die eindeutig bestimmte Untergruppe von G mit Index d. Ist G unendlich, so ist hei die eindeutig bestimmte Untergruppe von G mit Index 1.

2.16 Anwendung des Satzes von Lagrange Sei G eine endliche Gruppe. Ist die Gruppenordnung bekannt, so kann man die Ordnung eines Elementes g von G bestimmen, indem man nach dem kleinsten Teiler x von jGj sucht, fur den g x = 1 gilt. Dies kann man z.B. erreichen, indem man alle Teiler von jGj ausprobiert.

2.16.1. U bung Entwickele einen Algorithmus, der die Ordnung eines Elementes der Sn berechnet. ! 1 2 3 4 5 6 7 8 Z.B. n = 8, jSn j = 8!, g = 1 3 2 5 6 4 8 7 In der Kryptographie ist n  252 ublich.

Man kann dieses Verfahren noch beschleunigen. Hierzu benutzt man das folgende Ergebnis.

2.16.2. Satz Sei jGj = m1m2


mk eine Faktorisierung der Ordnung von G in ein Pro-

dukt paarweise teilerfremder naturlicher Zahlen mi , 1  i  k. Dann ist die Ordnung eines Elementes g 2 G das Produkt der Ordnungen der Elemente g jGj=mi , 1  i  k.

Version 6. August 1996

37

Beweis: Sei Mix= jGj=mi, xi die Ordnung von gi = gMi , 1 m i  k und x die Ordnung

von g . Dann ist gi i = 1 und nach dem Satz von Lagrange ist gi i = 1 fur 1  i  k. Daher ist xi ein Teiler von mi und von x fur 1  i  k. Weil die mi paarweise teilerfremd sind, ist das Produkt der xi ein Teiler von x. Andererseits gibt es ganze Zahlen ai , 1Qk i  k mit k xiai a1M1 + : : :+ ak Mk = 1. Daher ist gx


xk = g (a M +:::+ak Mk )(x


xk ) = Q gi 1

1

1

Daraus folgt die Behauptung.

1

i=1

j=1; xj j6=i

= 1.

Eine weitere Anwendung des Satzes von Lagrange besteht in der schnelleren Berechnung von diskreten Logarithmen. Sei hierzu G zyklisch mit Erzeuger a. Sei auerdem b 2 G. Es soll ein Exponent x gefunden werden mit ax = b. Teilerfremde Zerlegung von jGj. DL fur Primzahlpotenzen. U bung: Lose auf diese Weise das Entscheidungsproblem.

2.17 Normalteiler und Faktorgruppen Sei G eine Gruppe mit Untergruppe U .

2.17.1. De nition Die Untergruppe U heit Normalteiler, wenn aU = Ua gilt fur alle

a 2 G.

Man schreibt U  G.

2.17.2. Satz Genau dann ist U ein Normalteiler, wenn aUa;1  U fur alle a 2 G. Ist U ein Normalteiler, so ist fur alle a 2 G die Rechtsnebenklasse Ua gleich der Linksnebenklasse aU . Diese nennt man daher Nebenklasse .

(

!

)

2.17.3. Beispiel G = GL(2; ZZ) = ac db j a; b; c; d 2 ZZ; ad ; bc = 1 , ( ! ) a b SL(2; ZZ) = c d j a; b; c; d 2 ZZ; ad ; bc = 1  G, da: M 2 SL(2; ZZ); N 2 G; det(MNM ;1) = det(M )
det(N )
(det(M ));1 = 1. 2.17.4. Satz Ist U ein Normalteiler von G, so bilden die Nebenklassen von U in G eine Gruppe bezuglich der Komplexmultiplikation.

Beweis: Abgeschlossenheit: (aU )(bU ) = a(Ub)U = a(bU )U = abU . Assoziativitat: klar. neutrales Element: eU . inverses Element: a;1 U .

Version 6. August 1996

38

2.17.5. De nition Ist U ein Normalteiler von G, so heit die Gruppe der Nebenklassen von U in G Faktorgruppe von G nach U , in Zeichen G=U .

2.17.6. Beispiel GL(2; ZZ)=SL(2; ZZ) =

(

!

!

1 0 SL(2; ZZ); 1 0 SL(2; ZZ) 0 1 0 ;1

)

2.17.7. Satz Ist H eine weitere Gruppe und ' : G ! H ein Homomorphismus, so ist G0 = Kern ' ein Normalteiler von G und die Abbildung G=G0 ! Bild', aG0 7! '(a) ist ein Isomorphismus.

2.18 Erzeugendensysteme Sei G eine Gruppe und S  G.

2.18.1. De nition

1. Die von S erzeugte Gruppe ist der Durchschnitt aller Untergruppen von G, die S enthalten. Sie wird mit hS iG bezeichnet, bzw. mit hS i, falls G klar ist.

2. Ist hS i = G, so heit S Erzeugendensystem von G. 3. Hat G ein endliches Erzeugendensystem, so heit G endlich erzeugt.

2.18.2. Beispiel (ZZ; +) = h1i ) ZZ endlich erzeugt. 2.18.3. Satz Es ist h;i = feg. Ist S 6= ;, so besteht hS i aus allen endlichen Potenzprodukten von Elementen aus S .

2.18.4. Beispiel Fur SL(2; ZZ) := fA 2 ZZ22j det(A) = 1g gilt: SL(2; ZZ) =

*

!

1 1 ; 0 1 0 1 ;1 0

!+

:

2.19 Operation von Gruppen auf Mengen Sei X eine Menge und G eine Gruppe.

2.19.1. De nition Wir sagen, da G auf X operiert, wenn es eine Abbildung
: GX ! X , (g; x) 7! g
x gibt mit

1. (gh)
x = g
(h
x),

Version 6. August 1996

39

2. ex = x fur alle x 2 X und g; h 2 G.

2.19.2. Beispiel f!2 Sn ; hf iSn = G; X = f1; : : :; ng; (f j; i) 7! f j (i),

f = 11 23 32 44 ; (f 2; 3) 7! f 2(3) = 3 f i (f j (k)) = f i+j (k); f 0(k) = k ) G operiert auf X .

2.19.3. Satz In der Situation von De nition 2.19.1 ist R = f(x; y) 2 X  X : Es gibt g 2 G mit y = gxg  eine Aquivalenzrelation.

Die A quivalenzklassen von R aus Satz 2.19.3 heien G-Orbits oder G-Bahnen von X . Die Menge X ist disjunkte Vereinigung ihrer G-Orbits.

!

2.19.4. Beispiel f = 11 23 32 44 2 S4. hf i-Orbits von X = f1; 2; 3; 4g sind f1g; f2; 3g; f4g.

2.20 Die symmetrische Gruppe

Sn

Sei n eine naturliche Zahl.

2.20.1. De nition Fur r paarweise verschiedene Zahlen a1; : : :; ar aus f1; : : :; ng bezeichnet (a1; : : :; ar ) die Permutation der Sn , die ai auf ai+1 abbildet fur i < r und ar auf a1 . Diese Permutation heit r-Zykel. 2-Zykeln heien Transpositionen.

2.20.2. Beispiel f =

1 2 3 4 1 3 2 4

!

= (2; 3)

Transpositionen haben die Ordnung 2. Zykel der Lange 1 heien trivial . Die anderen heien nicht trivial.

2.20.3. Satz Die Sn+1 ist disjunkte Vereinigung der Nebenklassen (i; n + 1)Sn, 1  i  n + 1.

Beweis: Sei f 2 Sn+1. Dann ist (f (n + 1); n + 1)  f 2 Sn und f = (f (n + 1); n + 1)2  f . Also ist Sn+1 Vereinigung der Nebenklassen (i; n + 1)Sn , 1  i  n + 1. Diese Vereinigung ist disjunkt, weil die Transposition das Bild von n + 1 bestimmt.

Version 6. August 1996

40

2.20.4. Korollar Es gilt jSn+1j = (n + 1)jSnj, jSnj = n!. 2.20.5. Korollar Jede Permutation ist Produkt von Transpositionen. 2.20.6. U bung Der Beweis von Satz 2.20.3 enthalt einen Algorithmus zur Zerlegung einer Permutation in ein Produkt von Transpositionen. Man formuliere und analysiere diesen Algorithmus.

2.20.7. De nition Zwei Zykel (x1; : : :; xr) und (y1; : : :; ys) heien elementfremd, wenn der Durchschnitt der Mengen fx1 ; : : :; xr g und fy1 ; : : :; ys g leer ist.

2.20.8. Satz Jede Permutation f 6= (1) kann als Produkt elementfremder nicht trivialer Zyklen geschrieben werden. Diese Darstellung ist bis auf die Reihenfolge eindeutig.

Beweis: Sei f 2 Sn . Die Abbildung (f j ; i) 7! f j (i) de niert eine Operation von hf i

auf f1; : : :; ng. Also zerfallt f1; : : :; ng in paarweise disjunkte hf i-Orbits. Ist f 6= (1) so hat wenigstens ein Orbit mehr als ein Element. Fur einen solchen nicht trivialen Orbit Y de niere die Permutation fY durch fY (i) = f (i), falls i 2 Y und fY (i) = i andernfalls. Dann sind die fY elementfremde nicht triviale Zyklen und f ist das Produkt der fY . Sei eine weitere Zerlegung von f gegeben und sei g ein Zyklus, der in dieser Zerlegung vorkommt. Dann gibt es genau einen nicht trivialen hf i-Orbit Y , auf dem g nicht die Identitat ist. Hierfur gilt g = fY .

2.20.9. Beispiel f = 13 22 34 48 56 65 77 81 hf i-Orbits: f1| ; 3{z; 4; 8}g; f2g; f|{z} 5; 6 g; f7g Y1

!

Y2

fY = (1; 3; 4; 8); fY = (5; 6); f = fY  fY 1

2

1

2

2.20.10. Satz Die Anzahl der Permutationen, in die eine Permutation faktorisiert werden kann, ist stets gerade oder stets ungerade.

Beweis: Fur f 2 Sn setze

Y f (i) ; f (j ) : i ; j 1i liegt. Ware der Rest 0, so ware f im Ideal. s>1: Bestimme Erzeuger des Ideals (K [x] euklidisch), dann Division mit Rest. n>1: K [x] ist i.a. kein HIR (aber ZPE). Demonstriere Divisionsalgorithmus an Beispielen: 1. f = xy 2 + 1; f1 = xy + 1; f2 = y + 1, setze a1 = y f ; a1 f1 = ;y + 1, setze a2 = ;1 ;y + 1 ; a2f2 = 2, setze r = 2 =) xy 2 + 1 = (y (xy + 1) ; 1(y + 1) + 2, d.h. Rest: 2. 2. f = x2 y + xy 2 + y 2; f1 = xy ; 1; f2 = y 2 ; 1, setze a1 = x f ; a1 f1 = xy2 + x + y 2, setze a1 = x + y xy 2 + x + y 2 ; yf1 = x + y 2 + y , setze a2 = 1 und r = x y 2 + y ; f2 = y + 1, setze r = x + y + 1 =) f = (x + y )f1 + f2 + (x + y + 1), d.h. Rest: x + y + 1. 3. f = x2 y + xy 2 + y 2; f1 = y 2 ; 1; f2 = xy ; 1, setze a2 = x f ; a2f2 = xy2 + x + y 2, setze a1 = x xy 2 + x + y 2 ; a1f1 = 2x + y2 , setze a1 = 1 und r = 2x y 2 ; 1f1 = 1, setze r = 2x + 1 =) Rest: 2x + 1. =) Rest hangt von der Reihenfolge der Polynome ab! 90

Version 6. August 1996

91

5.2 Monomordnungen Sei x = x1


xn n Monom mit  = (1 ; : : :; n ) 2 ZZn0 . Die Abbildung ZZn0 ;! fMonomg,  7;! x ist Bijektion. 1

5.2.1. De nition Eine Monomordnung auf K [x1; : : :; xn] ist eine Relation < auf ZZn0 mit:

1. < ist lineare (totale) Ordnung auf ZZn0 , d. h. 8; ; 2 ZZn0 : ( = ) __ ( > ) __ ( < ), ( < ; < ) )  < . 2. Fur  < und 2 ZZn0 gilt:  + < + (Monotonie)

3. < ist Wohlordnung auf ZZn0 , d.h. jede nichtleere Teilmenge von ZZn0 besitzt ein kleinstes Element unter teilbar.

5.6.3. De nition Sei F = (f1; : : :; fs) eine Folge von Polynomen. Dann bezeichnet f F

den Rest der Division von f durch f1 ; : : :; fs (in dieser Reihenfolge). Ist G = fg1; : : :; gtg eine Grobnerbasis, so ist der Rest unabhangig von der Reihenfolge der gi und wird mit f G bezeichnet. Man sagt "f reduziert uber G\.

5.6.4. Korollar Sei G = fg1; : : :; gtg Grobnerbasis. Dann gilt f G = 0 , f 2 hg1; : : :; gti. Beweis: ): klar. (: f = f + 0 mit f 2 I = hg1; : : :; gti ) f G = 0. 5.6.5. Beispiel

1. Fur Erzeugendensystem F = fx2 y ; y 2 ; x4y 2 ; y 2 g  K [x; y ] gilt mit lexikographischer Ordnung: x5 yF = xy 3 . Der Divisionsalgorithmus liefert x5 y = (x3 + xy )(x2y ; y 2 ) + 0
(x4 y 2 ; y 2 ) + xy 3 . 2. Sei F = fx2y ; 2y 2 + x; x3 ; 2xy g. F(ist keine Grobnerbasis, weil (I )i x(x2y ; 2y 2 + x) ; y (x3 ; 2xy) = x2 22= hhLT x2y; x3i (Ausloschung)

5.6.6. De nition f; g 2 K [x1; : : :; xn]; f; g 6= 0. 1. Sei multideg (f ) =  und multideg (g ) = . Dann heit x , mit = ( 1; : : :; n) mit

i = max(i ; i), kleinstes gemeinsames Vielfaches von LM (f ) = x und LM (g ) = x . Schreibweise: x = kgV(LM (f ); LM (g)) = lcm(LM (f ); LM (g)). 2. S (f; g ) = LTx (f )
f ; LTx (g)
g heit S-Polynom von f und g .

5.6.7. Beispiel Sei f = x2y ; y2 und g = x4y2 ; y2. Dann = (4; 2) und das

S-Polynom ist S (f; g ) = xx yy
(x2 y ; y 2 ) ; xx yy
(x4y 2 ; y 2 ) = ;x2 y 3 + y 2. 4 2

4 2 2

4 2

5.6.8. Lemma Sei eine Summe von folgender Form gegeben: iP cix(i)gi mit ci 2 K und =1 t

(i) + multideg(gi) =  2 cjk , so da mit x jk

ZZn0 fur ci

Xt i=1

6= 0. Falls multideg

cix(i)gi =

X j;k

 Pt

i=1

ci x(i)gi



<  , so gibt es

cjk x; jk S (gj ; gk );

= kgV (LM (gj ); LM (gk)). Jedes cjk x; jk S (gj ; gk ) hat multideg <  .

Version 6. August 1996

98

  t Beweis: Sei di = LC (gi), s.d. cidi = LC cix(i)gi . Es gilt: P cidi = 0 (sonst hat i=1

Pt c x(i)g Multigrad = ). De niere p = x i gi , p hat Leitkoezient 1. Betrachte die i i i i di ( )

i=1

Reihe:

t X

cix(i)gi =

t X

cidipi = c1d1(p1 ; p2) + (c1 d1 + c2d2)(p2 ; p3) + : : : i=1 +(c1d1 + : : : + ct;1dt;1 )(pt;1 ; pt) + (|c1d1 + :{z: : + ct dt)} pt =0 Sei nun LT (gi) = di x (i) und (i) + (i) =  , d.h. LM (gi) j x ; 8i ) kgV (LM (gj ); LM (gk )) j x . Also ist x; jk Monom, und i=1

!

es gilt:

x jk g ; x jk g j ; gk ) = LT (gj ) j LT (gk ) k   = x (j ) gj ; x (k) gk dj x dk x  ( j )  (k ) = x d gj ; x d gk = pj ; pk j k Weil pj und pk Multigrad =  haben mit Leitkoezient 1 und weil die Dierenz pj ; pk Multigrad <  hat, folgt die Behauptung. x; jk S (g

x; jk

5.6.9. Satz SeiG I  K [x1; : : :; xn] Ideal. Eine Basis G = fg1; : : :; gtg ist eine Grobnerbasis , S (gi; gj ) = 0; 8i 6= j .

Beweis: ): klar, nach Korollar 5.6.4.

(: Sei f 2 I . zz: Alle S-Polynome lassen Rest 0. Dann gilt: LT (f ) 2 hLT (g1); : : :; LT (gt)i. Pt Gelte also f 2 I ) f = hi gi . Dann gilt multideg (f )  i=1 max (multideg {z (higi)}). Wahle ;:::;n | i=1

m(i)

hi so, da i=1 max (multideg (higi)) minimal wird, nenne das Minimum  . ;:::;n Beh: multideg (f ) =  . Bew: (durch Widerspruch) Ann: Es gilt multideg (f ) <  . Dann gilt: f = =

X

m(i)=

X

hi gi +

X

m(i)