1 Algebra
1.1 Einfuhrung
Einfuhrung 1
• Unter Algebra versteht man den Teilbereich der Mathematik, der sich mit dem Studium der Ei-genschaften von (Rechen-)Operationen beschaftigt.
. Genauer werden verschiedene Klassen von algebraischen Strukturen mittels Axiomen definiert
– Axiom: nicht zubeweisende Grundannahme/Pramisse/Hypthose, z.B. in PL formuliert
und deren Eigenschaften (d.h. logische Inferenzen aus den Axiomen) und Beziehungen untereinan-der untersucht.
. Anwendungen der Algebra in der Informatik:
– Kryptographie: RSA- und DLP-basierte Kryptosysteme
– Theoretische Informatik & Programmiersprachen: algebraische Sprachtheorie, formale Seman-tik, statische Analyse, Compilerbau, abstrakte Datentypen
Algebraische Strukturen 2
• Eine algebraische Struktur S ist dabei zunachst eine Struktur im Sinne der Pradikatenlogik, dienur Funktionen/Operatoren, jedoch keine Pradikate/Relationen definiert:
– US ist die Grundmenge/das Universum/der Trager
– IS interpretiert jedes Funktionssymbol f mit Aritat ar(f) als eine konkrete k-stellige Funk-
tion/Operation IS(f) : Uar(f)S → US auf US ; nullstellige Funktionssymbole mit Konstanten
gleichgesetzt.
• Konventionen:
– Meistens gibt man eine algebraische Struktur als Tupel 〈U, f1, . . . , fk〉 an.
Je nach Literatur auch mit runden Klammern (U, f1f2, . . . , fk).
Definiert dann einmalig die Interpretationen/Bedeutungen US und fSi .
Verwendet dann jedoch U und fi im Sinne von US und fSi .
. 〈U, f1, . . . , fk〉 (manchmal auch nur 〈f1, . . . , fk〉) wird als Signatur (=”nichtlogische“ Zei-
chen/Symbole) der algebraischen Struktur bezeichnet.
. Haufig gibt man die Aritat als Superskript in der Signatur direkt an, also 〈U, far(f1)1 , . . . , f
ar(fk)k 〉.
Algebraische Strukturen 3
• Beispiele
– 〈Q,+2, •2, 00, 10〉 mit Q die rationalen Zahlen und der Interpretation von + bzw. • als dieAddition bzw. Multiplikation auf den rationalen Zahlen und 0 bzw. 1 als die rationalen ZahlenNull bzw. Eins.
– 〈R,+2, •2, 00, 10〉 mit R die reellen Zahlen und der Interpretation von + bzw. • als die Additionbzw. Multiplikation auf den reellen Zahlen und 0 bzw. 1 als die reellen Zahlen Null bzw. Eins.
– 〈2A,∪2,∩2〉 mit 2A die Potenzmenge der Menge A und der Interpretation von ∪ und ∩ alsVereinigung bzw. Schnitt.
1
– 〈R>0, •2, 10〉 mit R die reellen Zahlen und der Interpretation von • als die Multiplikation auf
den reellen Zahlen und 1 als die reelle Zahl Eins.
– 〈Z,+2, 00〉 mit Z die ganzen Zahlen und der Interpretation von + als die Addition auf denganzen Zahlen und 0 als die ganze Zahl Eins.
– 〈AA, ◦2, Id0A〉 mit AA die Menge der Funktionen von A nach A und der Interpretation von ◦
als Funktionskompositionen und IdA als die Identitatsfunktion auf A.
– 〈Σ∗, •2, ε0〉 mit Σ∗ die Menge der endlichen Worter uber dem Alphabet Σ und der Interpre-tation von • als Konkatenation und ε als das leere Wort.
Algebraische Strukturen 4
• Beispiele
– 〈RR,+2, •2〉mit RR die Menge aller Funktionen von R nach R und der Interpretation von + und• als punktweise Addition bzw. Multiplikation ((f+g)(x) = f(x)+g(x), (f •g)(x) = f(x)•g(x)).
– 〈⋃k≥0{a, b}k, extend
2, push1a, push
1b , pop
1, ()0〉 mit {a, b}∗ die Menge der endlichen Tupel (Lis-ten) mit Eintragen aus {a, b} und der Interpretation von extend als Konkatenation zweierListen, pushx als das Anfugen des Elements x an den Anfang der Liste, pop das Entfernen desersten Eintrags einer nicht leeren Liste und () der leeren Liste.
– 〈2Σ∗ ,∪2, •2, ∅0, {ε}0〉 mit 2Σ∗ die Menge aller Mengen/Sprachen endlicher Worter uber demAlphabet Σ und der Interpretation von ∪ als Mengenvereinigung, • als Konkatenation vonSprachen (d.h. L1 •L2 = {uv | u ∈ L1, v ∈ L2}), ∅ als die leere Menge und {ε} als die Menge,die genau das leere Wort enthalt.
– 〈Q[X],+2, •2, 00, 10〉 mit Q[X] die Menge aller univariaten Polynome mit rationalen Koeffizi-enten in einer Variablen X und der Interpretation von + und • als die ubliche Addition bzw.Multiplikation von Polynomen und 0 und 1 als die jeweiligen rationalen Zahlen.
Algebraische Strukturen 5
• Weitere Bemerkungen/Konventionen:
– Ein Term/Ausdruck uber einer gegebenen Signatur und dessen Syntaxbaum ist analog zur PLdefiniert, z.B. fur 〈N0, f
2, g1, a0〉 sind”f(g(0), 1)“,
”g(f(f(a, g(a)), g(a)))“,
”a“ Terme.
– Fur binare Operatorsymbole, insbesondere +, •,⊕,� u.a. wird meistens die Infixnotation stattder Prafixnotation verwendet, z.B. also
”(a • b)“ statt
”•(a, b)“.
Insbesondere wird das Symbol”•“ haufig (wenn keine Missverstandnisse entstehen konnen)
dann auch einfach weggelassen, z.B. statt”•(a, b)“ einfach
”ab“.
– Beachte: Die Operatoren mussen stets wieder Elemente aus der Grundmenge zuruckgegeben,was als Abgeschlossenheit bezeichnet wird.
• Algebraische Strukturen werden nach den Axiomen (Eigenschaften), die ihre Operatoren erfullen,z.B. Assoziativitat, Kommutativitat, siehe auch semantische Aquivalenzen in AL/PL, klassifiziert.
Grundlegende algebraische Strukturen (Uberblick) 6
• Def.: Eine Halbgruppe ist eine algebraische Struktur 〈A, •2〉 mit:
1. • assoziativ ist, d.h. es gilt ∀a, b, c : (a • (b • c)) = ((a • b) • c).
〈A, •2〉 ist eine kommutative Halbgruppe, falls zusatzlich zu 1 gilt:
2. • kommutativ ist, d.h. es gilt ∀a, b : (a • b) = (b • a).
2
. Bei assoziativen Operatoren spielt die Reihenfolge der Auswertung eines Terms keine Rolle, so dassauf die Klammern verzichtet werden kann.
• Def.: Ein (kommutatives) Monoid ist eine alg. Struktur 〈A, •2, 10〉 mit
1. 〈A, •2〉 eine (kommutative) Halbgruppe und
2. neutralem Element 10 (bzgl. •), d.h. es gilt ∀a : (a • 1) = a = (1 • a).
. Beispiele:
– Monoide:
〈R,+2, 00〉, 〈R>0, •2, 10〉, 〈Z,+2, 00〉, 〈Σ∗, •2, ε0〉, 〈N0,+
2, 00〉, 〈AA, ◦2, Id0A〉
– Halbgruppen ohne neutrales Element: 〈R>0,+2〉 (bzgl. Addition auf R), 〈N,+2〉 (bzgl. Addi-
tion auf N).
– Keine Halbgruppe: 〈N, pow2〉 mit pow(a, b) = ab z.B. (23)4 6= 2(34).
Grundlegende algebraische Strukturen (Uberblick) 7
• Def.: Eine (kommutative) Gruppe ist eine alg. Struktur 〈A, •2, 10〉 mit:
1. 〈A, •2, 10〉 ein (kommutatives) Monoid und
2. Inversen (bzgl. •), d.h. es gilt ∀a∃b : (a • b) = 1 = (b • a).
Eine kommutative Gruppe wird auch als abelsche Gruppe bezeichnet.
. Beispiele:
– Kommutative Gruppen: 〈R,+2, 00〉, 〈R>0, •2, 10〉, 〈Z,+2, 00〉.
– Keine Gruppen: 〈Σ∗, •2, ε0〉, 〈N0,+2, 00〉, 〈AA, ◦2, IdA〉
. Die Bijektionen SA = {f : A → A | f bijektiv } von A nach A bzgl. der Funktionskomposi-tion und der Identitat bilden jedoch die sogenannte symmetrische Gruppe, welche i.A. nichtkommutativ ist (spater mehr).
Grundlegende algebraische Strukturen (Uberblick) 8
• Def.: Ein (unitarer) Ring ist eine alg. Struktur 〈A,+2, •2, 00〉 (bzw. 〈A,+2, •2, 00, 10〉) mit:
1. 〈A, •2〉 eine Halbgruppe (bzw. 〈A, •2, 10〉 ein Monoid) und
2. 〈A,+2, 00〉 eine kommutative Gruppe und
3. • distributiert uber + von beiden Seiten, d.h. es gilt ∀a, b, c : (a • (b+ c)) = (a • b+ a • c)∧ ((a+b) • c) = ((a • c) + (b • c)).
• Def.: Ein Korper ist eine alg. Struktur 〈A,+2, •2, 00, 10〉 mit:
1. 〈A,+2, •2, 00, 10〉 ein unitarer Ring und
2. 〈A \ {0}, •2, 10〉 eine kommutative Gruppe.
. Beachte: In einem Korper hat bis auf 0 jedes Element ein Inverses bzgl. •.
. Beispiele:
– unitare Ringe, keine Korper: 〈Z,+2, •2, 00, 10〉, 〈Q[X],+2, •2, 00, 10〉
〈2Σ∗ ,∪2, •2, ∅0, {ε}0〉 (nicht kommutativ)
– Korper: 〈R,+2, •2, 00, 10〉, 〈Q,+2, •2, 00, 10〉
3
Grundlegende algebraische Strukturen (Uberblick) 9
• Def.: Ein Verband ist eine alg. Struktur 〈A,t2,u2〉 mit:
1. 〈A,t2〉 kommutative Halbgruppe und
2. 〈A,u2〉 kommutative Halbgruppe und
3. es gelten die Absorptionsgesetze ∀a, b, c : a u (a t b) = a = a t (a u b).
Ein Verband ist distributiv, falls zusatzlich noch gilt:
4. ∀a, b, c : a u (b t c) = (a u b) t (a u c)
. Beispiele:
– keine Verbande: 〈R,+2, •2〉, 〈Q,+2, •2〉, 〈N0,+2, •2〉
– distributive Verbande: 〈2A,∪2,∩2〉, 〈R,min2,max2〉, 〈N, ggT2, kgV2〉,
〈{0, 1}{0,1}N ,∧2,∨2〉 boolsche Funktionen/Semantik der AL mit
[F ∧G](β) := min{[F ](β), [G](β)} und
[F ∨G](β) := max{[F ](β), [G](β)}.
Grundlegende algebraische Strukturen (Uberblick) 10
• Eine konkrete algebraische Struktur ist dann z.B. eine Gruppe, falls sie ein Modell der Definitioneiner Gruppe im Sinne der PL ist.
. Z.B. ist S = 〈U, g2, e0〉 eine Gruppe, falls S im Sinne der PL ein Modell der Formel
FG := ∀x∀y∀z(g(x, (g(y, z)) = g(g(x, y), z))∧ ∀x(g(x, e) = x ∧ g(e, x) = x)∧ ∀x∃y(g(x, y) = e ∧ g(y, x) = e)
ist (ggf. mit entsprechender Umbenennung der Symbole).
• Die Definition von Halbgruppe, Monoid, Gruppe, Ring, Korper und Verband werden auch alsabstrakte algebraische Strukturen bezeichnet.
Grundlegende algebraische Strukturen (Uberblick) 11
• Die Algebra ist vorrangig an Aussagen F interessiert, die z.B. in allen Gruppen oder in allenVerbanden gelten – im Sinne der PL also logische Inferenzen der jeweiligen Axiome sind (z.B.FG |= F ).
• Z.B. kann man zeigen (ohne Beweis):
Lemma: In jedem Verband 〈A,t2,u2〉 gilt:
1. ∀a : a u a = a = a t a (Idempotenz)
2. In jedem distributiven Verband gilt auch: ∀a, b, c : a t (b u c) = (a t b) u (a t c).
• Eine weitere haufige Fragestellung ist die nach den schwachsten Anforderungen/Annahmen FA,aus denen eine konkrete Eigenschaft F stets logisch folgt.
. Nach obigem Lemma konnte man z.B. auf die entsprechenden semantischen Aquivalenzen in derAL/PL verzichten.
. Je weniger Annahmen/Axiomen, umso weniger Arbeit, um nachzuweisen, dass eine konkrete Struk-tur z.B. eine Gruppe oder ein Verband ist.
• Wir betrachten im Weiteren die wichtigsten Eigenschaften von Gruppen, welche auch fur die Kryp-trographie von Interesse sind.
4
1.2 Gruppentheorie
1.2.1 Zahlentheoretische Grundlagen
Erinnerung: Primfaktorzerlegung, ggT, kgV, Teilbarkeit 12
• Im Weiteren a, b,N ∈ Z mit N > 0.
• a|b kurz fur ∃k ∈ Z : b = k • a (”a teilt b (ohne Rest)”)
• ggT(a, b) := max{d ∈ N : d|a ∧ d|b} (”großter gemeinsamer Teiler”)
kgV(a, b) := min{m ∈ N : a|m ∧ b|m} (”kleinstes gemeinsames Vielfaches”)
a • b = kgV(a, b) • ggT(a, b)
• Primzahlen P = {p ∈ N : p > 1 ∧ ∀n ∈ N : n|p→ (n = 1 ∨ n = p)}
Fur p ∈ P sei νp(n) := max{k ∈ N0 : pk|n}.
Dann ist∏p∈P p
νp(n) die Primfaktorzerlerung von n ∈ N.
• ggT(a, b) =∏p∈P p
min{νp(a),νp(b)} und kgV(a, b) =∏p∈P p
max{νp(a),νp(b)}
. Beispiel: a = 300 = 22 • 3 • 52, b = 126 = 2 • 32 • 7
ggT(a, b) = 21 • 31 • 50 • 70 = 6
kgV(a, b) = 22 • 32 • 52 • 7 = 6300
ggT(a, b) • kgV(a, b) = 37800 = a • b
Erinnerung: modN , ZN , Z∗N 13
• ZN := {0, 1, 2, . . . , N − 1} (vgl. [N ] = {1, 2, . . . , N})
•”Division mit Rest”:
a mod N : eindeutige Zahl k ∈ ZN mit N |(a− k).
a ≡N b kurz fur a mod N = b mod N
. Erinnerung: ≡N ist Aquivalenzrelation auf Z mit Aquivalenzklassen
[k]n = k + nZ := {k + nz | z ∈ Z}
• Z∗N := {k ∈ ZN | ggT(k,N) = 1}.
ϕ(N) := |Z∗N | (Euler’s phi-function)
Lemma: Es gilt ϕ(N) = N∏p∈P : p|N (1− p−1)
Insbesondere ϕ(p) = p− 1 fur p ∈ P.
(Beweis mittels Kombinatorik/Siebformel, siehe TA.)
. Bsp.: ϕ(15) = 15(1− 15 )(1− 1
3 ) = (5− 1)(3− 1) = 8.
Erweiterter euklidischer Algorithmus (EEA) 14
• Wichtig fur Kryptographie:
ggT(a, b) kann effizient rekursiv auf ohne Kenntnis der Primfaktorzerlegungen von a und b berechnetwerden.
. Beobachtungen:
5
1. ggT(a, b) = ggT(b, a) = ggT(−a, b) = ggT(a,−b) = ggT(−a,−b),
daher oBdA 0 ≤ a ≤ b.
2. ggT(a, b) = b falls a = 0
3. ggT(a, b) = 1 falls a = 1 (prinzipiell uberflussig wegen 2 ).
4. ggT(a, b) = ggT(b mod a, a) fur 1 < a ≤ b da:
Es gilt b mod a = b− ka fur k = bb/ac.
Damit: d|a ∧ d|b gdw. d|a ∧ d|(b− ka).
Erweiterter euklidischer Algorithmus (EEA) 15
• Dies fuhrt auf den euklidischen Algorithmus:
def euclid(a,b):if a < 0:
a = -aif b < 0:
b = -bif b < a:
return euclid(b,a)if a == 0:
return bif a == 1:
return 1return euclid(b % a, a)
Erweiterter euklidischer Algorithmus (EEA) 16
• Wichtig(er) fur Kryptographie und Algebra:
Der euklidische Algorithmus kann so erweitert werden, dass er zwei Zahlen α, β ∈ Z bestimmt, sodass gilt
ggT(a, b) = α • a+ β • b
. Beobachtungen (oBdA 0 ≤ a ≤ b):
1. ggT(a, b) = b = 0 • a+ 1 • b falls a = 0; also α = 0, β = 1.
2. ggT(a, b) = 1 = 1 • a+ 0 • b falls a = 1; also α = 1, β = 0.
3. ggT(a, b) = (β′ − bb/acα′)a+ α′b
falls 1 < a ≤ b und rekursiv ggT(b mod a, a) = α′ • (b mod a) + β′ • a
da: Es gilt b mod a = b− ka fur k = bb/ac Daher:
ggT(a, b) = ggT(b mod a, a) = α′(b mod a) + β′a= α′(b− ka) + β′a = (β′ − kα′)a+ α′b
(Da 0 ≤ b mod a < a terminiert die Rekursion.)
. Bemerkung: kompakter fur a > 0
1,2 ggT(a, b) = a = 1 • a+ 0 • b falls b mod a = 0; also α = 1, β = 0.
6
Erweiterter euklidischer Algorithmus (EEA) 17
• Dies fuhrt auf den erweiterten euklidischen Algorithmus (EEA)
def eea(a,b):if a < 0:
alpha,beta = eea(-a,b)return (-alpha,beta)
if b < 0:alpha,beta = eea(a,-b)return (alpha,-beta)
if b < a:beta,alpha = eea(b,a)return (alpha,beta)
if a == 0:return (0,1)
if a == 1:return (1,0)
alpha,beta = eea(b % a, a)return (beta - (b // a) * alpha,alpha) # (β′ − bb/acα′, α′)
. Ohne Beweis: man kann zeigen, dass der EEA maximal log2(a+ b) rekursive Aufrufe benotigt.
Erweiterter euklidischer Algorithmus (EEA) 18
• Kurzfassung EEA
Gegeben: 1 ≤ a ≤ b aus N
– Falls (b mod a) = 0, gibt α = 1, β = 0 zuruck.
– Ansonsten berechne rekursiv α′, β′ mit
ggT(b mod a, a) = (b mod a)α′ + aβ′
Gib dann α = (β′ − bb/acα′), β = α′ zuruck.
• Beispiel: a = 5, b = 911 mit ggT(5, 911) = 1 (911 ist prim)
a b bb/ac α β5 911 182 −182 11 5 − 1 0
Test: 1 = ggT(5, 911)!= 5 • (−182) + 911 • 1 = 1[1mm]
Erweiterter euklidischer Algorithmus (EEA) 19
• Kurzfassung EEA
Gegeben: 1 ≤ a ≤ b aus N
– Falls (b mod a) = 0, gibt α = 1, β = 0 zuruck.
– Ansonsten berechne rekursiv α′, β′ mit
ggT(b mod a, a) = (b mod a)α′ + aβ′
Gib dann α = (β′ − bb/acα′), β = α′ zuruck.
• Beispiel: a = 45 = 5 • 32, b = 63 = 7 • 32 mit ggT(45, 63) = 9
a b bb/ac α β45 63 1 3 −218 45 2 − 2 19 18 − 1 0
Test: 9 = ggT(45, 63)!= 45 • 3 + 63 • (−2) = 9
7
1.2.2 Einleitung
Gruppen – Definition (Erinnerung) 20
• Definition: G=〈G, •, 1〉 ist eine Gruppe, falls
0. • : G×G→ G (abgeschlossen),
1. ∀a, b, c : a • (b • c) = (a • b) • c (assoziativ),
2. ∀a : a • 1 = 1 • a = a (Neutrales) und
3. ∀a∃b : a • b = b • a = 1 (Inverses).
G ist endlich, falls |G| <∞;G ist kommutativ (auch: abelsch), falls zusatzlich noch:
4. ∀a, b : a • b = b • a.
. Anmerkung:
– Multiplikative Notation 〈G, •, 1〉 fur allgemeine, d.h. auch nicht kommutative Gruppen; haufigkurz ab statt a • b.
– Additive Notation 〈G,+, 0〉 nur fur kommutative Gruppen.
– Obige Definition ist (semantisch) aquivalent zu der Definition, in der die Axiome 2 und 3
abgeschwacht werden zu:
2’ ∀a : a • 1 = a (Rechtsneutrales) und 3’ ∀a∃b : a • b = 1 (Rechtsinverses).
Gruppen – Beispiele: Gruppen auf Z 21
• Beispiel: 〈Z,+, 0〉
– Grundmenge: Ganze Zahlen Z = {. . . ,−2,−1, 0, 1, 2, . . .}
– Gruppenoperation: kanonische Addition auf Z
– Neutrales: 0
– Inverse: −a
• Beispiel: 〈nZ,+, 0〉 fur n ∈ N
– Grundmenge: nZ = {. . . ,−2n,−1n, 0, 1n, 2n, . . .} ganzzahlige Vielfache von n
– Gruppenoperation: kanonische Addition auf Z (abgeschlossen?)
– Neutrales: 0
– Inverse: −a
. Bemerkung: Da 〈nZ,+, 0〉 und 〈Z,+, 0〉 bzgl. derselben Gruppenoperation definiert sind undnZ ⊆ Z gilt, nennt man 〈nZ,+, 0〉 auch eine Untergruppe von 〈Z,+, 0〉 (spater mehr).
Gruppen – Beispiele: Gruppen auf Zn 22
• Beispiel: 〈Zn,+n, 0〉 additive Gruppe modulo n ∈ N
– Grundmenge: Zn = {0, 1, . . . , n− 1} Reste modulo n ∈ N
– Gruppenoperation: a+n b := (a+ b) mod n
– Neutrales: 0
– Inverse: 0 fur 0, sonst n− a fur a ∈ Zn \ {0}
• Beispiel: 〈Z∗n, •n, 1〉 multiplikative Gruppe modulo n ∈ N
8
– Grundmenge: Z∗n = {x ∈ Zn | ggT(x, n) = 1} alle zu n teilerfremden Reste modulo n
– Gruppenoperation: a • nb := (a • b) mod n
– Neutrales: 1
– Inverse: α mod n inverse zu a mit 1 = ggT(a, n) = α • a+ β • n (EEA)
. Beweise spater.
Gruppen – Beispiele: Gruppen auf Zn 23
• 〈Z6,+6, 0〉:+6 0 1 2 3 4 50 0 1 2 3 4 51 1 2 3 4 5 02 2 3 4 5 0 13 3 4 5 0 1 24 4 5 0 1 2 35 5 0 1 2 3 4
• 〈Z∗9, •9, 1〉:•9 1 2 4 5 7 81 1 2 4 5 7 82 2 4 8 1 5 74 4 8 7 2 1 55 5 1 2 7 8 47 7 5 1 8 4 28 8 7 5 4 2 1
Gruppen – Beispiele: Gruppen auf Kurven 24
• Beispiel: Addition auf Einheitskreis bzgl. f(t) := (sin t, cos t)
– Grundmenge: {(x, y) ∈ R2 | x2 + y2 = 1}
– Gruppenoperation: f(t1)⊕ f(t2) := f(t1 + t2) – Addition der Winkel im Bogenmaß gemessenim Uhrzeigersinn ab (0, 1) (
”12 Uhr“).
– Neutrales: f(0) = (0, 1)
– Inverse: −f(t) := f(−t)
. Ubung: Uberprufen, dass alle Gruppenaxiome erfullt sind.
P0 := (sin 0, cos 0) = f(0)P1 := (sin π
4 , cos π4 ) = f(π4 )
P2 := (sin π3 , cos π3 ) = f(π3 )
P1 ⊕ P2 := (sin 7π12 , cos 7π
12 ) = f(π4 + π3 )
Gruppen – Beispiele: Gruppen auf R 25
• Beispiel: 〈R,+, 0〉 additive Gruppe der reellen Zahlen
– Grundmenge: reelle Zahlen R bzw. positive reelle Zahlen R>0
– Gruppenoperation: kanonische Addition bzw. Multiplikation
9
– Neutrales: 0
– Inverse: −a
• Beispiel: 〈R>0, •, 1〉 multiplikative Gruppe der positiven reellen Zahlen
– Grundmenge: positive reelle Zahlen R>0
– Gruppenoperation: kanonische Multiplikation
– Neutrales: 1
– Inverse: 1/a
. Beachte: x•y = e(log x)+(log y) und x+y = log(ex •ey), d.h. man kommt von 〈R,+, 0〉 nach 〈R>0, •, 1〉mittels x 7→ ex und zuruck mittels x 7→ log x. Solche Gruppen werden isomorph genannt (spatermehr).
. Entsprechend von 〈Z6,+6, 0〉 nach 〈Z∗9, •9, 1〉 mittels k 7→ 2k mod 9; Umkehrabbildung wird alsdiskreter Logarithmus zur Basis 2 bezeichnet.
Gruppen – Beispiel: Permutationen 26
• Erinnerung:
Eine Bijektion f : A→ A wird auch als Permutation von A bezeichnet.
Fur die Menge aller Permutationen einer Menge A schreibt man SA.
Mit Sn := S[n] bezeichnet man speziell die Menge aller Permutationen von [n].
• Beispiel: 〈SA, ◦, IdA〉 symmetrische Gruppe uber A.
– Grundmenge: SA = {f : A→ A | f bijektiv }
– Gruppenoperation: Funktionskomposition f ◦ g : A→ A : a 7→ f(g(a))
– Neutrales: Identitat IdA : A→ A : a 7→ a
– Inverse: Umkehrabbildung
• Die symmetrischen Gruppen sind i.A. nicht kommutativ.
• Jede Gruppe G lasst sich als ein Teil der SG auffassen (Satz von Cayley).
• Gerade fur die Gruppentheorie ist die Zykelschreibweise von Permutationen besonders nutzlich.
Gruppen – Beispiel: Permutationen 27
• Erinnerung (TA5.2, HA61, HA6.3): Sei f ∈ Sn eine Permutation von [n].
In der Zykelschreibweise notiert π, indem man die Kreise/Zyklen angibt, in die der Graph Gπ =([n], {(i, f(i)) | i ∈ [n]}) zerfallt:
f = (x(1)0 , x
(1)1 , . . . , x
(1)l1−1)(x
(2)0 , x
(2)1 , . . . x
(2)l2−1) . . . (x
(k)0 , x
(k)1 , . . . x
(k)lk−1)
Jedes Tupel (Zykel/Zyklus) (x(j)0 , x
(j)1 , . . . , x
(j)lj−1) gibt gerade einen der Kreise in Gπ an, d.h. es gilt
f(x(i)j ) = x
(i)(j+1) mod li
.
• Beispiel:
f =
1 7→ 22 7→ 33 7→ 14 7→ 4
= (1, 2, 3) (4) =
1
2
3
4
g =
1 7→ 12 7→ 33 7→ 24 7→ 4
= (1) (2, 3) (4) =
1
2
3
4
10
• Die Zykel konnen beliebig angeordnet werden, die Elemente in einem Zykel konnen zyklisch rotiertwerden, d.h.:
(2)(1, 3, 5)(4) = (2)(4)(5, 1, 3) = (3, 5, 1)(4)(2)
Gruppen – Beispiel: Permutationen 28
• Beispiel: 〈S3, ◦, Id〉
(1)(2)(3) (1, 2)(3) (1, 3)(2) (1)(2, 3) (1, 2, 3) (1, 3, 2)(1)(2)(3) (1)(2)(3) (1, 2)(3) (1, 3)(2) (1)(2, 3) (1, 2, 3) (1, 3, 2)(1, 2)(3) (1, 2)(3) (1)(2)(3) (1, 3, 2) (1, 2, 3) (1)(2, 3) (1, 3)(2)(1, 3)(2) (1, 3)(2) (1, 2, 3) (1)(2)(3) (1, 3, 2) (1, 2)(3) (1)(2, 3)(1)(2, 3) (1)(2, 3) (1, 3, 2) (1, 2, 3) (1)(2)(3) (1, 3)(2) (1, 2)(3)(1, 2, 3) (1, 2, 3) (1, 3)(2) (1)(2, 3) (1, 2)(3) (1, 3, 2) (1)(2)(3)(1, 3, 2) (1, 3, 2) (1)(2, 3) (1, 2)(3) (1, 3)(2) (1)(2)(3) (1, 2, 3)
. Ublicherweise notiert man die Fixpunkte (Kreise der Lange 1) jedoch nicht:
Id[3] (1, 2) (1, 3) (2, 3) (1, 2, 3) (1, 3, 2)Id[3] Id[3] (1, 2) (1, 3) (2, 3) (1, 2, 3) (1, 3, 2)(1, 2) (1, 2) Id[3] (1, 3, 2) (1, 2, 3) (2, 3) (1, 3)(1, 3) (1, 3) (1, 2, 3) Id[3] (1, 3, 2) (1, 2) (2, 3)(2, 3) (2, 3) (1, 3, 2) (1, 2, 3) Id[3] (1, 3) (1, 2)
(1, 2, 3) (1, 2, 3) (1, 3) (2, 3) (1, 2) (1, 3, 2) Id[3]
(1, 3, 2) (1, 3, 2) (2, 3) (1, 2) (1, 3) Id[3] (1, 2, 3)
Additive Gruppe modulo n: 〈Zn,+n, 0〉 29
• Lemma: 〈Zn,+n, 0〉 ist eine kommutative Gruppe (n > 0):
1. Abgeschlossen: a+n b = (a+ b) mod n ∈ Zn nach Definition von modn.
2. Assoziativ: Seien a, b ∈ Zn.
Dann gilt (a+ b) mod n = a+ b− kn fur k := b(a+ b)/nc.
Damit: (a+n b) +n c = ((a+ b− kn) + c) mod n = (a+ b+ c) mod n
Symmetrisch folgt a+n (b+n c) = (a+ b+ c) mod n.
3. Neutrales: a+n 0 = (a+ 0) mod n = a mod n = a fur a ∈ Zn.
4. Inverse: 0 +n 0 = (0 + 0) mod n = 0 mod n = 0 und a +n (n − a) = (a + (n − a)) mod n =0 mod n = 0 (a ∈ Zn \ {0}).
5. Kommutativ: a+n b = (a+ b) mod n = (b+ a) mod n = b+n a.
. Ubung:
〈Zn, •n, 1〉 ist ein kommutatives Monoid (vollkommen analog).
〈Zn,+n, •n, 0〉 ist ein kommutativer Ring.
Multiplikative Gruppe modulo n: 〈Z∗n, •n, 1〉 30
• 〈Zn,+n, •n, 0, 1〉 ist i.A. jedoch kein Korper, z.B.:
•6 0 1 2 3 4 50 0 0 0 0 0 01 0 1 2 3 4 52 0 2 4 0 2 43 0 3 0 3 0 34 0 4 2 0 4 25 0 5 4 3 2 1
11
• Allgemein haben nur die zu n teilerfremden Reste ein Inverses bzgl. •n da:
– Aus 1 = a • nb folgt ggT(ab, n) = ggT(a • nb, n) = ggT(1, n) = 1.
. Also auch 1 = ggT(a, n) = ggT(b, n).
. Nullteiler: Falls 1 < d := ggT(a, n), dann a • nnd = a
d• nn = 0.
. Mussen •n auf Z∗n einschranken, z.B. •6 nur auf Z∗6 = {1, 5}:
•6 1 51 1 55 5 1
Multiplikative Gruppe modulo n: 〈Z∗n, •n, 1〉 31
• Lemma: 〈Z∗n, •n, 1〉 ist eine kommutative Gruppe (n > 1).
1. Abgeschlossen: Fur p ∈ P gilt: p|n ∧ p|ab gdw. p|n ∧ (p|a ∨ p|b).
Aus ggT(a, n) = 1 = ggT(b, n) = 1 folgt also
1 = ggT(ab, n) = ggT(ab mod n, n).
2. Assoziativ: analog zu 〈Zn,+n, 0〉.
3. Neutrales: ∀a : a • n1 = 1 — analog zu 〈Zn,+n, 0〉.
4. Inverse: EEA berechnet α, β ∈ Z mit:
1 = ggT(a, n) = aα+ nβ
Setze b := (α mod n) (damit sicher in Z∗n), dann
a • nb = (a • b) mod n (Def. von •n)= (a • (α+ kn)) mod n (α mod n ∈ α+ nZ)= (aα+ akn+ nβ) mod n (nβ mod n = 0)= (1 + akn) mod n = 1 (1 = aα+ nβ)
d.h. b = (α mod n) ist das Inverse zu a in 〈Z∗n, •n, 1〉.
5. Kommutativ: analog zu 〈Zn,+n, 0〉.
Erweiterter euklidischer Algorithmus (EEA) 32
• Beispiel: a = 5, b = 911 mit ggT(5, 911) = 1 (911 ist prim)
a b bb/ac α β5 911 182 −182 11 5 − 1 0
Nach EEA: 1 = ggT(5, 911) = 5 • (−182) + 911 • 1
. Also ist 729 = (−182) mod 911 das Inverse von 5 in 〈Z∗911, •911, 1〉:
5 • 911729 = (5 • 729) mod 911 = 3645 mod 911 = (1 + 4 • 911) mod 911 = 1
• Erinnerung: Aber 906 ist das Inverse von 5 in 〈Z911,+911, 0〉:
5 +911 906 = (5 + 906) mod 911 = 911 mod 911 = 0.
und 0.2 das Inverse von 5 in 〈R>0, •, 1〉
und −5 das Inverse von 5 in 〈R,+, 0〉
und . . .
• Anmerkung: 〈Zn,+n, •n, 0, 1〉 Korper gdw. Zn \ {0} = Z∗n gdw. n ∈ P.
12
1.2.3 Restklassengruppen
Restklassengruppen, Kongruenzen 33
• Erinnerung: Sei f : A→ B Funktion. Dann ist
”a ≡f b gdw. f(a) = f(b)“
eine Aquivalenzrelation auf A mit Aquivalenzklassen [a]f = f−1(f(a)).
. Fur f(x) = x mod n (n ∈ N) erhalt man damit sofort:
”a ≡n b gdw. (a mod n) = (b mod n)“
ist Aquivalenzrelation auf Z mit Klassen [a]n = {a+ nz | z ∈ Z} =: a+ nZ.
Man nennt [a]n auch die Restklasse von a modulo n.
. Insbesondere ist ≡n eine Kongruenz bzgl. + und •, d.h. es gilt
a+ b ≡n a′ + b′ und a • b ≡n a′ • b′
fur a ≡n a′ und b ≡n b′ da:
Mit a′ = a+ nk fur k = a′−an und b′ = b+ nl fur l = b′−b
n folgt, dass
– a′ + b′ = (a+ nk) + (b+ nl) = a+ b+ n(k + l) und
– a′b′ = (a+ nk) • (b+ nl) = ab+ n(al + bk + nkl).
Restklassengruppen, Kongruenzen 34
• Daher sind durch
[a]n + [b]n := [a+ b]n und [a]n • [b]n := [a • b]n
Funktionen/binare Operationen auf Z/nZ = {[x]n | x ∈ Z} wohldefiniert.
. D.h. die Definitionen sind unabhangig von dem konkreten Reprasentanten einer Restklasse sind,d.h. dass fur a ≡n a′ und b ≡n b′ gilt:
– [a]n + [b]n := [a+ b]n!= [a′ + b′]n =: [a′]n + [b′]n und
– [a]n • [b]n := [ab]n!= [a′b′]n =: [a′]n • [b′]n
was, wie gerade nachgerechnet, der Fall ist (ansonsten keine Funktionen).
• Addition und Multiplikation sind trivial auf Z/nZ assoziativ und kommutativ, da sie mittels derAddition und Multiplikation auf Z definiert wurden, z.B.:
[a]n + ([b]n + [c]n) = [a]n + [b+ c]n = [a+ (b+ c)]n = [a+ b+ c]n
. Erinnerung: In der AL/PL hatten wir das Ersatzbarkeitstheorem (z.B. (F ∧G) ≡ (F ∧H), falls G ≡H). Die semantische Aquivalenz kann daher analog als Kongruenz bzgl. der logischen Operatorenangesehen werden.
Restklassengruppen, Kongruenzen 35
• Beispiel: 〈Z/nZ,+, [0]n〉 fur n ∈ N
– Grundmenge: Z/nZ := {[a]n | a ∈ Z}
– Gruppenoperation: [a]n + [b]n := [a+ b]n
– Neutrales: [0]n
13
– Inverse: −[k]n = [−k]n
• Beispiel: 〈(Z/nZ)∗, •, [1]n〉 fur n ∈ N
– Grundmenge: (Z/nZ)∗ := {[a]n | ggT(a, n) = 1}
– Gruppenoperation: [a]n • [b]n := [a • b]n
– Neutrales: [1]n
– Inverse: [a]−1n = [α]n mit 1 = ggT(a, n) = α • a+ β • n (EEA).
. Bemerkung: 〈Z/nZ,+, •, [0]n, [1]n〉 ist ein kommutativer Ring.
. Bemerkung: Entsprechend kann man z.B. auch 〈R/2πZ,+2π, [0]2π〉 definieren mit”x ≡2π y gdw.
x−y2π ∈ Z“. Die
”Kreisgruppe“ 〈{(x, y) ∈ R2 | x2 + y2 = 1},⊕, (0, 0)〉 verhalt sich dann zu
〈R/2πZ,+2π, 0〉 wie 〈Zn,+n, 0〉 zu 〈Z/nZ,+, [0]n〉 (Reprasentanten/Aquivalenzklassen).
Restklassengruppen, Kongruenzen 36
• Fakt: Es gilt
[a+n b]n = [(a+ b) mod n]n = [a+ b]n = [a]n + [b]n und
[a • nb]n = [(a • b) mod n]n = [a • b]n = [a]n • [b]n
. Anwendung: Statt in 〈Z∗n, •n, 1〉 zu rechnen, rechne in 〈(Z/nZ)∗,+, [1]n〉.
In 〈(Z/nZ)∗,+, [1]n〉 kann man sich die Reprasentanten noch auswahlen, was die Rechnung haufigvereinfacht.
. Z.B. 5 • 1312 = 8 mittels:
[5 • 1312]13 = [5]13 • [12]13 = [5]13 • [−1]13 = [−5]13 = [8]13
oder kurz: 5 • 12 ≡13 5 • (−1) ≡13 −5 ≡13 8
. Z.B. 994 • 997995 • 997996 = 991 mittes:
[994 • 997995 • 997996]997 = [994]997 • [995]997 • [996]997
= [−3]997 • [−2]997 • [−1]997 = [−6]997 = [991]997
oder kurz: 994 • 995 • 996 ≡997 (−3) • (−2) • (−1) ≡997 −6 ≡997 991
1.2.4 Grundlegende Eigenschaften
Gruppen – Eigenschaften (1) 37
• Lemma: Sei G=〈G, •, 1〉 eine Gruppe. Dann gilt stets (ab fur a • b):
– Das Neutrale ist eindeutig da:
Sei 1′ ∈ G mit ∀a ∈ G : 1′a = a = a1′.
Da 1 Neutrales gilt auch ∀a ∈ G : 1a = a = a1.
Damit: 1′ = 1′1 = 1
– Das Inverse ist eindeutig da:
Sei a ∈ G beliebig und b, c ∈ G mit ab = ba = ac = ca = 1.
Damit: b = b1 = b(ac) = (ba)c = 1c = c
Notation: Fur multiplikative Gruppen 〈G, •, 1〉 schreibt man a−1 fur das (jetzt) eindeutigeInverse von a ∈ G; fur additive Gruppen 〈G,+, 0〉 entsprechend −a.
14
Wichtig:”a−1“ bedeutet
”Bestimme das Inverse“, z.B. in 〈Z∗5, •5, 1〉 also 3−1 = 2 ∈ Z∗5 und
nicht 0.3 6∈ Z∗5.
. (a−1)−1 = a und (ab)−1 = b−1a−1 da:
a und (a−1)−1 Inverse von a−1; (ab)−1 und b−1a−1 Inverse von ab.
In additiver Notation: −(−a) = a und −(a+ b) = (−b) + (−a).
Gruppen – Eigenschaften (2) 38
• Lemma: Sei G=〈G, •, 1〉 eine Gruppe. Dann gilt stets (ab fur a • b):
– Kurzungsregel: Falls ab = ac, dann bereits b = c da:
b = 1b = (a−1a)b = a−1(ab) = a−1(ac) = (a−1a)c = 1c = c
Analog: Falls ba = ca, dann auch b = c
. Trivial: Falls b = c, dann auch ab = ac
Also: b = c gdw. ab = ac fur ein beliebiges a ∈ G
bzw.: b 6= c gdw. ab 6= ac fur ein beliebiges a ∈ G
• Folgerungen:
– a−1b ist die eindeutige Losung von ax = b da:
ax = b = a(a−1b), also x = a−1b nach Kurzungsregel.
. Entsprechend ba−1 eindeutige Losung von xa = b.
– Fur jedes a ∈ G sind la(x) := ax und ra(x) := xa Permutationen von G:
a−1b ist das eindeutige Urbild von b bzgl. la.
ba−1 ist das eindeutige Urbild von b bzgl. ra.
1.2.5 Ordnung eines Elements
Ordnung eines Elements 39
• Definition: Fur G=〈G, •, 1〉 eine Gruppe, a ∈ G und k ∈ N0:
a0 := 1 und ak+1 := a • (ak) und a−(k+1) := (a−1) • (a−k)
Setze dann 〈a〉 := {ak | k ∈ Z}
und ord(a) := min{k ∈ N | ak = 1} (mit min ∅ :=∞).
ord(a) heißt Ordnung von a und ist die kleinste positive Zahl mit ak = 1.
• Anmerkungen:
– Fur additiv geschriebene Gruppen 〈G,+, 0〉 wird die Definition zu
0a := 0 und (k + 1)a := a+ (ka) und (−(k + 1))a := (−a) + ((−k)a)
mit 〈a〉 = {ka | k ∈ Z} und ord(a) = min{k ∈ N | ka = 0}.
– Der Exponent zahlt nach Definition einfach, wie viele Kopien des Elements a bzw. a−1 manmittels der Gruppenoperation verknupfen muss.
Man rechnet also im Exponenten ganz normal in 〈Z,+, •, 0, 1〉.
15
. Ubung: Insbesondere gilt fur alle a ∈ G und k, l ∈ Z:
(ak)−1 = a−k = (a−1)k akal = ak+l 〈a〉 = 〈a−1〉 ord(a) = ord(a−1)
Ordnung eines Elements 40
• Beispiel: ord((1, 2, 3)) = 3 in 〈S3, ◦, id〉 da:
(1, 2, 3)3 = ((1, 2, 3) ◦ (1, 2, 3)) ◦ (1, 2, 3) = (1, 3, 2) ◦ (1, 2, 3) = (1)(2)(3)
• Beispiel: ord(5) = 6 in 〈Z∗7, •7, 1〉 da:
56 = (5 • 75) • 754 = 4 • 754
= (4 • 75) • 753 = 6 • 753
= (6 • 75) • 752 = 2 • 752
= (2 • 75) • 75= 3 • 75= 1
Oder einfacher mittels 5 ≡7 −2, woraus direkt 5k ≡7 (−2)k folgt.
• Beispiel:
ord(4) = 3 in 〈Z6,+6, 0〉 da (4 +6 4) +6 4 = 2 +6 4 = 0 und
ord(4) =∞ in 〈Z,+, 0〉 da 〈4〉 = 4Z = {4k | k ∈ Z}
Ordnung eines Elemente: Veranschaulichung fur |G| <∞ 41
• Erinnerung: la(x) = ax und ra(x) = xa sind Permutationen auf G.
Betrachte Gra = (G, {(x, ra(x)) | x ∈ G}) (alternativ Gla) (Zykelnotation).
Gra zerfallt wieder in disjunkte Kreise (siehe auch Cayley-Graph in TA13.4):
. Beispiele:
〈Z6,+6, 0〉, a = 1
4
3
2
15
0
〈Z6,+6, 0〉, a = 2
43
2
1
5
0
〈Z∗9, •9, 1〉, a = 2
4
8
2
1
5
7
〈Z∗9, •9, 1〉, a = 4
4
8
2
1
5
7
. 〈a〉 sind gerade die Elemente des Kreises, der das Neutrale enthalt;
ord(a) = |〈a〉| ist gerade die Lange des Kreises;
Gra−1 entsteht durch Umdrehen der Kanten von Gra .
. Beobachtung: Alle Kreise von Gra haben dieselbe Lange ord(a);
Gra besteht aus genau |G|ord(a) ∈ Z Kreisen (siehe spater).
Ordnung eines Elemente: Veranschaulichung fur |G| <∞ 42
16
〈S3, ◦, Id〉, a = (1, 2, 3)
Id
(1, 2, 3)
(1, 3, 2)
(1, 2)
(2, 3)
(1, 3)
〈Z∗7, •7, 1〉, a = 5
1
5
4
6
2
3
〈Z6,+6, 0〉, a = 4
0
4
2
1
5
3
〈Z12,+12, 0〉, a = 3
03
6
9
1
47
10
2
5
8
11
Ordnung eines Elements 43
• Lemma: Sei 〈G, •, 1〉 eine Gruppe und a ∈ G mit ord(a) <∞.
Dann gilt: (Erinnerung: ord(a) = min{k ∈ N : ak = 1} ≥ 1.)
1. a−1 = aord(a)−1 da 1 = aord(a) = aord(a)−1 • a.
2. ak = ak mod ord(a) fur jedes k ∈ Z da
k mod ord(a) = k −m ord(a) fur ein geeignetes m ∈ Z, so dass
ak = a(k mod ord(a))+m ord(a) = ak mod ord(a)(aord(a))m = ak mod ord(a) • 1m
3. 〈a〉 = {1, a, a2, . . . , aord(a)−1} da (2) auf Definition anwenden:
〈a〉 = {ak | k ∈ Z} = {ak mod ord(a) | k ∈ Z} = {ak | k ∈ Zord(a)}
4. |〈a〉| = ord(a) da:
Nach 3 gilt |a| ≤ ord(a). Falls |〈a〉| < ord(a), dann gibt es 0 ≤ i < j < ord(a) mit ai = aj , alsoaj−i = 1, womit ord(a) ≤ j − i < ord(a) folgt.
Bemerkung: Selbes Argument wie in TA5.2(b).
5. ak = ak mod ord(a) = 1 gdw. k mod ord(a) = 0 gdw. ord(a)|k da
ord(a) = ord(a−1) = min{k ∈ N | ak = 1} und 0 ≤ k mod ord(a) < ord(a).
Ordnung eines Elements 44
• Erinnerung: 〈a〉 = 〈a−1〉 in jeder Gruppe.
17
• Beispiel: 〈Z∗11, •11, 1〉:〈1〉 = {1}〈2〉 = {2, 4, 8, 5, 10, 9, 7, 3, 6, 1}〈3〉 = {3, 9, 5, 4, 1}〈4〉 = 〈3〉〈5〉 = {5, 3, 4, 9, 1}〈6〉 = 〈2〉〈7〉 = {7, 5, 2, 3, 10, 4, 6, 9, 8, 1}〈8〉 = 〈7〉〈9〉 = 〈5〉〈10〉 = {10, 1}
. Also ord(2) = ord(6) = ord(7) = ord(8) = 10, ord(3) = ord(5) = ord(8) = ord(9) = 5, ord(10) = 2,ord(1) = 1.
Ordnung eines Elements 45
• Erinnerung: 〈a〉 = 〈a−1〉 in jeder Gruppe.
• Beispiel: 〈S3, ◦, id〉:〈(1)(2)(3)〉 = {(1)(2)(3)}〈(1)(2, 3)〉 = {(1)(2, 3), (1)(2)(3)}〈(1, 2)(3)〉 = {(1, 2)(3), (1)(2)(3)}〈(1, 3)(2)〉 = {(1, 3)(2), (1)(2)(3)}〈(1, 2, 3)〉 = {(1, 2, 3), (1, 3, 2), (1)(2)(3)}〈(1, 3, 2)〉 = 〈(1, 2, 3)−1〉
• Fakt: Ist π ∈ Sn eine Permutation, die in Zykelschreibeweise die Form
π = (x(1)1 , . . . , x
(1)l1
)(x(2), . . . , x(2)l2
) . . . (x(r), . . . , x(r)lr
)
hat, dann gilt:ord(π) = |〈π〉| = kgV(l1, l2, . . . , lr)
Intuition: r Uhren, i-te Uhr braucht li Zeiteinheiten fur einen Durchlauf.
Ordnung eines Elements 46
• Satz: Sei 〈G, •, 1〉 eine endliche Gruppe.
Dann gilt fur jedes a ∈ G, dass |G| mod ord(a) = 0, also a|G| = 1.
. Erinnerung: ra(x) = xa ist Permutation, Gra = (G, {(x, xa) | x ∈ G}).
. Beweis: Fixiere ein a ∈ G und definiere x〈a〉 := {xak | k ∈ Z} fur x ∈ G.
x〈a〉 = {rka(x) | k ∈ Z} ist gerade der Kreis in Gra , der x enthalt.
1.”x ∼a y gdw. x〈a〉 = y〈a〉“ ist eine Aquivalenzrelation auf G.
(”Liegen im selben Kreis in Gra .“)
2. Die Aquivalenzklasse [x]a = {y ∈ G | x ∼a y} ist gerade x〈a〉.
(”Der Kreis von x in Gra .“)
3. Jede Aquivalenzklasse [x]a hat gerade ord(a) = |〈a〉| viele Elemente.
Da Multiplikation 〈a〉 → x〈a〉 : y 7→ xy mit x bijektiv.
18
4. Damit gilt |G| = k ord(a) mit k = |{[x]a | x ∈ G}| die Anzahl der verschiedenen Aquivalenzklassen(”Kreise in Gra“).
5. Insbesondere gilt daher |G| mod ord(a) = 0 und somit a|G| = 1.
Ordnung eines Elements 47
• Beispiel: Fur 〈Z12,+12, 0〉 und a = 3 gilt 〈3〉 = {3, 6, 9, 0},
so dass”x ∼a y gdw. x+12 {0, 3, 6, 9} = y +12 {0, 3, 6, 9}“:
[0]3 = {0, 3, 6, 9} [1]3 = {1, 4, 7, 10} [2]3 = {2, 5, 8, 11}
Zum Vergleich Gr3 = (Z12, {(x, x+12 3) | x ∈ Z12}):
03
6
9
1
47
10
2
5
8
11
Ordnung eines Elements 48
• Bemerkung: Fur 〈Z,+, 0〉 und a = 3 gilt 〈3〉 = 3Z,
so dass”x ∼3 y gdw. x+ 3Z = y + 3Z gdw. x ≡3 y“.
Die Kongruenz ≡n modulo n ist also ein Spezialfall von ∼a.
Alternativ kann man x ∼a y daher auch als”x und y unterscheiden sich (von rechts) um eine
Potenz von a lesen“.
(∼a ist i.A. allerdings nur eine Kongruenz, falls a mit jedem Element aus G kommutiert.)
Ordnung eines Elements 49
• Korollar: Sei 〈G, •, 1〉 eine endliche Gruppe. Dann gilt:
1. λG := kgV({ord(a) | a ∈ G}) teilt |G| ohne Rest.
2. λG = min{λ ∈ N | ∀a ∈ G : aλ = 1}.
Man nennt λG den Gruppenexponent von G.
3. Fur jedes k ∈ Z, jedes a ∈ G und M = |G| (oder M = λG):
ak = a(k mod M)+mM = a(k mod M)(aM )m = ak mod M
. Beispiel: In 〈Z∗11, •11, 1〉 mit |Z∗11| = ϕ(11) = 11− 1
21001 = 21001 mod |Z∗11| = 21 = 2
Weiterhin gilt ord(2) = 10 und daher λZ∗11 = |Z∗11| = 10.
. Beispiel: In 〈S6, ◦, Id〉 mit |S6| = 6! = 720.
(1, 2, 3, 4, 5, 6)723 = (1, 2, 3, 4, 5, 6)723 mod |S6|
= (1, 2, 3, 4, 5, 6)3 = (1, 4)(2, 5)(3, 6)
Weiterhin gilt ord( (1, 2, 3, 4, 5, 6) ) = 6 und λS6= kgV([6]) = 60.
19
Ordnung eines Elements 50
• Spezialfall: In 〈Z∗n, •n, 1〉 Satz von Euler
1 = a|Z∗n| = aϕ(n)
bzw. aϕ(n) ≡n 1 falls ggT(a, n) = 1.
• Spezialfall: In 〈Z∗p, •p, 1〉 fur p ∈ P kleiner fermatscher Satz
1 = a|Z∗p| = aϕ(p) = ap−1
bzw. ap−1 ≡p 1 falls ggT(a, p) = 1.
• Anwendung: Gegeben endliche Gruppe 〈G, •, 1〉. Gesucht e, d ∈ Z, so dass
f(x) = xe und g(x) = xd Permutationen von G mit f−1 = g.
Es soll also ∀x : x!= g(f(x)) = (xe)d = xed = xed mod |G| = xe•|G|d gelten.
Hinreichend hierfur: 1 = e • |G|d. (Notwendig: 1 = e • λGd.)
1 = e • |G|d bedeutet 1 = ggT(e, |G|) (siehe ggT, EEA).
Wahle also e ∈ Z∗|G| und bestimme d mittels EEA.
1.2.6 Untergruppen
Untergruppen 51
• Defintion: Sei 〈G, •, 1〉 eine Gruppe.
Eine nicht leere Teilmenge H ⊆ G wird als Untergruppe von G (kurz: H ≤ G) bezeichnet, falls •
eingeschrankt auf H eine Gruppe definiert.
• Beispiele:
– 〈a〉 definiert eine (kommutative) Untergruppe fur jedes a ∈ G.
Speziell fur 〈Z,+, 0〉: 〈n〉 = nZ.
– Z definiert eine Untergruppe von 〈R,+, 0〉
– Zn definiert keine Untergruppe von Z.
– Die Automorphismen eines Graphens mit n Knoten bilden eine Untergruppe jeder symme-trsichen Gruppe 〈Sm, ◦, id〉 mit mindestens m ≥ n Elementen.
. Spezialfall: Die Symmetrien des regelmaßigen n-Ecks definieren eine als Diedergruppe Dn
bezeichnete Untergruppe der 〈Sn, ◦, id〉 ([Bsp])
Das sind gerade die Graphautomorphismen des ungerichteten Kreises mit n Knoten.
Es gilt |Dn| = 2n, also S3 = D3, aber fur n > 3 echte Untergruppe.
Untergruppen 52
• Beispiel D4 ≤ S4 (siehe auch TA5.1)
20
Bildquelle: [wikipedia.de]
Untergruppen 53
• Lemma: Sei 〈G, •, 1〉 Gruppe und ∅ 6= H ⊆ G mit H ≤ G.
Dann erbt H das Neutrale und die Inversen von G, da:
– Sei 1H das Neutrale in H. Dann folgt 1H = 1, da in G gilt:
1H = 1H1 = 1H(1H1−1H ) = (1H1H)1−1
H = 1H1−1H = 1
– Weiterhin sind die Inversen in G eindeutig.
• Lemma: Sei 〈G, •, 1〉 Gruppe und ∅ 6= H ⊆ G. Dann gilt
H ≤ G gdw. ∀a, b ∈ H : ab−1 ∈ H
da:
– Es gelte H ≤ G: nach oben auch b−1 ∈ H und • auf H abgeschlossen.
– Es gelte ∀a, b ∈ H : ab−1 ∈ H.
Dann gilt aa−1 = 1 ∈ H und damit 1b−1 = b−1 ∈ H fur alle a, b ∈ H.
Wegen (b−1)−1 = b folgt ab = a(b−1)−1 ∈ H fur alle a, b ∈ H.
1.2.7 Zyklische Gruppen
Zyklische Gruppen 54
• Definition: Eine Gruppe 〈G, •, 1〉 heißt zyklisch,
falls es ein a ∈ G mit 〈a〉 = G gibt;
a heißt dann Erzeuger/Generator von G.
. Fakt:
Jede zyklische Gruppe ist kommutativ da ak • al = ak+l = alak.
. Beispiele:
– 〈Z,+, 0〉 ist zyklisch; Erzeuger 1 und −1.
– 〈Zn,+n, 0〉 ist zyklisch; Erzeuger Z∗n (folgt).
– 〈Sn, ◦, id〉 ist nicht zyklisch i.A., da nicht kommutativ fur n ≥ 3.
– 〈Z∗n, •n, 1〉 zykl. gdw. n ∈ {2, 4, pr, 2pr : p ∈ P \ {2}, r ∈ N} (ohne Beweis).
– 〈a〉 ist immer eine zyklische Untergruppe.
21
Zyklische Gruppen 55
• Lemma: Sei 〈G, •, 1〉 zyklisch und endlich mit N := |G|. Dann gilt fur a ∈ G:
〈a〉 = G gdw. ∀p ∈ {p ∈ P : p | N} : aN/p 6= 1
. Beweis:
Falls a Erzeuger, dann ord(a) = N , also aN/p 6= 1, da N/p < ord(a).
Falls a kein Erzeuger, ord(a) < N ∧ ord(a)|N . Wahle p ∈ P mit p | Nord(a) .
. Korollar 1: Jede Gruppe 〈G, •, 1〉 mit p := |G| ∈ P ist zyklisch.
da: (1) ord(a) ∈ {1, p} und (2) ord(a) = 1 gdw. a = 1.
Also 〈a〉 = G gdw. a 6= 1.
. Korollar 2: Z∗n ist gerade die Menge der Erzeuger von 〈Zn,+n, 0〉.
da: 〈a〉 6= Zn gdw. ∃p|n : np• na = 0 gdw. ∃p|n : p|a gdw. ggT(a, n) ≥ p > 1.
Zyklische Gruppen 56
• Lemma:
Jede Untergruppe H ≤ G einer zyklischen Gruppe 〈G, •, 1〉 ist zyklisch.
. Beweis: Sei 〈g〉 = G. OBdA. H 6= {1}.
1. Sei I = {k ∈ Z | gk ∈ H}. Da H ⊆ G = 〈g〉 gilt H = {gk | k ∈ I}.
2. Da H Gruppe: (1) k + l ∈ I fur k, l ∈ I, (2) k ∈ I gdw. −k ∈ I, (3) 0 ∈ I.
3. Sei m := min{k ∈ N : gk ∈ H} = min(I ∩ N) die kleinste positive Zahl in I.
4. Dann gilt auch mZ ⊆ I, da 〈gm〉 = {gk | k ∈ mZ} ⊆ H.
5. Wir zeigen, dass I = mZ und damit 〈gm〉 = H. Sei hierfur n ∈ I beliebig.
6. Dann gilt auch n+mZ ⊆ I, also auch n mod m ∈ I.
7. Da 0 ≤ n mod m < m und m = min(I ∩ N) folgt n mod m = 0.
. Korollar: Speziell fur G = 〈Z,+, 0〉 folgt H = I = mZ in obigem Beweis.
D.h. die zyklischen Untergruppen von 〈Z,+, 0〉 sind gerade von der Form 〈mZ,+, 0〉 fur m ∈ N0.
1.2.8 Homomorphie und Isomorphie
Homomorphie und Isomorphie 57
• Definition: Seien 〈GA, •A, 1A〉 und 〈GB , •B , 1B〉 Gruppen.
h : GA → GB heißt Homomorphismus, falls fur alle a, b ∈ GA
h(a • Ab) = h(a) • Bh(b)
Falls h bijektiv, nennt man h Isomorphismus und GA ∼= GB ismorph.
. Beispiele: Homomorphien (”von ahnlicher Gestalt“)
– h : 〈Z,+, 0〉 → 〈Z/nZ,+, [0]n〉 : z 7→ [z]n
– h : 〈R,+, 0〉 → 〈{(x, y) ∈ R2 | x2 + y2 = 1},⊕, (0, 1)〉 : x 7→ (sinx, cosx)
. Beispiele: Isomorphien (”von gleicher Gestalt“)
22
– 〈Z/nZ,+, [0]n〉 ∼= 〈Zn,+n, 0〉 und
〈(Z/nZ)∗, •, [1]n〉 ∼= 〈Z∗n, •n, 1〉
mittels h([k]n) = k mod n und h−1(k) = [k]n.
– 〈R,+, 0〉 ∼= 〈R>0, •, 1〉 mittels h(x) = ex und h−1(x) = log x.
Homomorphie und Isomorphie 58
• Lemma: Ist h : GA → GB ein Homomorphismus von Gruppen, dann gilt:
1. h(1A) = 1B da: 1B • Bh(1A) = h(1A) = h(1A • A1A) = h(1A) • Bh(1A).
2. h(a−1) = h(a)−1 da: h(a) • Bh(a)−1 = 1b = h(a • Aa−1) = h(a) • Bh(a−1).
3. h(〈a〉) = 〈h(a)〉 da: h(〈a〉) = {h(ak) | k ∈ Z} = {h(a)k | k ∈ Z} = 〈h(a)〉.
4. ord(a) ≥ ord(h(a)) (falls h Isomorphismus, dann ord(a) = ord(h(a)).
da: ord(a) = |〈a〉| ≥ |h(〈a〉)| = |〈h(a)〉| = ord(h(a)).
5. h(GA) ≤ GB da: h(x) • Bh(y)−1 = h(x • Ay−1) ∈ h(GA).
6. h−1(1B) ≤ GA da: h(x • Ay−1) = h(x) • Bh(y)−1 = 1B • 1B = 1B .
7. Ist h Isomorphismus, dann auch die Umkehrabbildung h−1
da: h−1(h(x) • Bh(y)) = h−1(h(x • Ay)) = x • Ay = h−1(h(x)) • Ah−1(h(y)).
8. Ist h Isomorphismus, dann 〈a〉 = GA gdw. 〈h(a)〉 = GB da: 4 .
Homomorphie und Isomorphie 59
• Lemma: Falls G = 〈g〉 = {gk | k ∈ Z} zyklische Gruppe, dann ist
– h : 〈Z,+, 0〉 → 〈G, •, 1〉 : k 7→ gk Homomorphismus,
sogar Isomorphismus, falls G nicht endlich.
Da: G = {gk | k ∈ Z} und gk • gl = gk+l.
– h : 〈Z|G|,+|G|, 0〉 → 〈G, •, 1〉 : k 7→ gk Isomorphismus, falls G endlich.
Da: G = {gk | k ∈ Z|G|} und gk • gl = g(k+l) mod |G| = gk+nl.
. Diskrete Version von 〈R,+, 0〉 ∼= 〈R>0, •, 1〉 mittels h(x) = ex.
(Allerdings sind 〈R,+, 0〉 und 〈R>0, •, 1〉 nicht zyklisch.)
. Korollar: {gk | k ∈ Z∗|G|} sind genau die Erzeuger von G = 〈g〉.
da: h : Z|G| → G : k 7→ gk Ismorphismus;
Isomormphismen bilden eindeutig Erzeuger auf Erzeuger ab;
Z∗n ist die Menge der Erzeuger von 〈Zn,+n, 0〉.
Homomorphie und Isomorphie 60
• Aus der Sicht der Gruppentheorie sind isomorphe Gruppen aquivalent – kennt man einen Isomor-phismus h : G1 → G2, so kann man sich prinzipiell aussuchen, in welcher der beiden Gruppen manrechnen mochte:
a • 1b = h−1(h(a)) • 1h−1(h(b)) = h−1(h(a) • 2h(b))
• Beispiele:
23
– [5 • 1312]13 = [5]13 • [12]13 = [8]13
also 5 • 1312 = 8
oder kurzer: 5 • 12 ≡13 5 • (−1) ≡13 −5 ≡13 8
– [995 • 997 . . . • 997995︸ ︷︷ ︸1000Faktoren
]997 = [995]1000997 = [−2]4997 = [16]997
also 9951000 mod 997 = 16
oder kurzer: 9951000 ≡997 (−2)4 ≡997 16
Homomorphie und Isomorphie 61
• Fur die Kryptographie ist aber auch die Frage der effizienten Berechnung eines Isomorphismus hbzw. h−1 wichtig.
. Diskreter-Logarithmus-Problem (DLP):
Gegeben 〈g〉 = G und a ∈ G, find das k ∈ Z|G| mit gk = a.
D.h. berechne h−1(a) fur h(k) = gk der kanonische Isomorphismus.
. Ubung: DLP ist trivial in 〈Zn,+n, 0〉 und in 〈Z,+, 0〉 (additive Notation!).
. Die Kryptographie ist gerade an zyklischen Gruppen interessiert, fur welche das DLP nicht effizientgelost werden kann.
Kandidaten: bestimmte zyklische Untergruppen von 〈Z∗p, •p, 1〉 fur p ∈ P; bestimmte zyklischeUntergruppen von elliptischen Kurven.
1.2.9 RSA, ElGamal
RSA 62
• Lemma: Sei 〈G, •, 1〉 eine endliche Gruppe.
Fur jedes feste k ∈ Z sei Ek : G→ G : a 7→ ak.
1. Falls k ≡|G| k′, dann sind Ek und Ek′ identisch da
Falls |G| |(k − k′), dann ∀a ∈ G : ak−k′
= 1 und ∀a ∈ G : ak = ak′
2. Falls ggT(k, |G|) = 1, dann ist Ek bijektiv und
es gilt E−1k = Ek′ fur jedes k′ ∈ Z mit k • k′ ≡|G| 1 da:
Ek(Ek′(a)) = akk′
= akk′ mod |G| = a.
• Erinnerung: Gruppenexponent λG, falls G endlich:
λG = kgV({ord(a) | a ∈ G}) = min{λ ∈ N | ∀a ∈ G : aλ = 1}
. Bemerkung: Mittels λG gilt genauer:
1. k ≡λG k′ gdw. Ek und Ek′ identisch
2. Ek ist bijektiv gdw ggT(k, λG) = 1
3. Gilt ggT(k, λG) = 1, dann gibt es ein k′ ∈ Zλ∗G mit E−1k = Ek′ .
Insbesondere kann k 6≡|G| k′ ∧ k ≡λG k′ gelten.
24
RSA 63
• Generische Basisversion von RSA:
1. Empfanger wahlt G so, dass er M = |G| (oder M = λG) berechnen kann;
wahlt dann k ∈ Z∗M und berechnet k′ ∈ Z∗M mit kk′ ≡M 1.
2. Empfanger veroffentlicht G und k in geeigneter Form.
3. Sender codiert Nachricht m in Gruppenelement a;
schickt das permutierte Element Ek(a) uber offentlichen Kanal.
4. Empfanger berechnet a = Ek′(Ek(a)) und gewinnt daraus wieder m.
• Zentrale Anforderung an G:
Allein unter der Kenntnis von G und Ek(a) ist es in einem realistischen Zeitraum”nicht moglich”a
(und daher auch nicht |G| , λG, k′) zu berechnen
. Kandidaten fur geeignete Gruppen G:
〈Z∗pq, •pq, 1〉 mit p 6= q sehr große Primzahlen. Es gilt∣∣Z∗pq∣∣ = (p− 1)(q − 1).
Empfanger veroffentlicht nur k und ausgewertetes Produkt N := pq.
RSA 64
• Beispiel fur p = 41, q = 43, N = pq = 1763:
Dann gilt ϕ(41 • 43) =∣∣Z∗pq∣∣ = (41− 1)(43− 1) = 23 • 5 • 2 • 3 • 7 = 1680.
Wahle z.B. k = 11 ∈ Z∗1680.
Mittels EEA:a b bb/ac α β11 1680 152 611 −48 11 1 −4 33 8 2 3 −12 3 1 −1 11 2 1 1 0
Also k′ = 611 mit 11 • 1680611 = 1.
”Verschlusseln” von 71: E11(71) = (7111) mod 1763 = 270
”Entschlusseln” von 270: E611(270) = (270611) mod 1763 = 71
ElGamal 65
• Generische Version von ElGamal:
1. Empfanger wahlt endliche zyklische Gruppe 〈G, •, 1〉 samt Erzeuger g.
Wahlt weiterhin zufalliges x ∈ Z|G| und berechnet hx = gx in G.
2. Empfanger veroffentlicht hx, g und”G“ in geeingeter Form
3. Sender codiert Nachricht m als Gruppenelement a.
Wahlt weiterhin zufalliges y ∈ Z|G| und berechnet hy = gy und c = hyx • a in G.
Verschickt dann hy und c uber offentlichen Kanal.
4. Empfanger berechnet h−xy • c = g−xy • gxy • a = a in G.
25
. Notwendige Forderung an G:
Berechnen von x aus hx bzw. y aus hy darf nicht in einem realistischen Zeitraum moglich sein, d.h.der inverse Ismorphismus zu Z|G| → G : k 7→ gk muss
”schwer“ zu berechnen sein (DLP).
. Kandidaten fur geeignete Gruppen G:
Bestimmte Untergruppen von 〈Z∗p, •p, 1〉 fur p prim; bestimmte Untergruppen elliptischer Kurven.
RSA, ElGamal – Anmerkungen 66
• RSA wird in der vorgestellten Form nur als Bausstein fur Verschlusselungsverfahren benutzt.
. Ublicherweise verwendet man RSA nur, um den Schlussel fur z.B. AES-basierte Verschlusselungsverfahrenauszutauschen.
. Fur die Einbettung von Binardaten in die Gruppe wird z.B. das randomisierte [Optimal AsymmetricEncryption Padding] verwendet.
• Fur ElGamal verwendet man meistens die Untergruppe 〈g2〉 von 〈Z∗p, •p, 1〉 fur 〈g〉 = Z∗p (p ∈ P).
. ElGamal wird ebenfalls hochstens zum Schlusselaustausch verwendet – meistens allerdings nur daszugrundeliegende Diffie-Hellman-Protokoll:
Hier wahlt der Sender nur y und sendet nur hy an den Empfanger. Aus hyx = gxy = hxy bestimmenbeide Parteien dann den gemeinsamen Schlussel fur z.B. AES-basierte Verschlusselungsverfahren.
• [Aktuelle Empfehlung] des BSI fur Sicherheit bis 2038:
Fur RSA p, q ≥ 21500.
Fur ElGamal/DLP in 〈Z∗p, •p, 1〉: p ≥ 23000
26