Processing math: 100%

Gruppen und Symmetrien: Vorlesung 21 ff.

1  Wiederholung: Der Abzählsatz von Pólya

1.1  Beispiel: Kette mit fünf Perlen

Auf wie viele bis auf Drehungen verschiedene Möglichkeiten lässt sich eine 5-perlige Kette mit den Farben Rot und Blau einfärben, sodass genau 2 rote und mindestens 1 blaue Perle auftauchen? Jede Perle soll hierbei entweder rot, blau oder aber gar nicht gefärbt werden. Zur Beantwortung solcher und ähnlicher Fragen wurde Pólyas Abzählsatz besprochen, der sich in folgender algorithmischen Weise anwenden lässt:

  1. Schritt: Bestimmung der Menge X und der auf ihr operierenden Gruppe G.
    • Hier ist X={1,2,3,4,5} die Menge der 5 Perlen und G=σ die Gruppe der 5 Drehungen erzeugt von σ=(1,2,3,4,5)

  2. Schritt: Bestimmung des Zyklentyps aller Elemente von G.
    • Hier ist σ0=(1)(2)(3)(4)(5), σ1=(1,2,3,4,5), σ2=(1,3,5,2,4), σ3=(1,4,2,5,3), σ4=(1,5,4,3,2).

  3. Schritt: Bestimmung des Zyklenzeigers ZG.
    • Hier ist ZG(s1,s2,s3,s4,s5)=15(s51+4s5) (die 4 5-Zykel σ1,σ2,σ3,σ4 tragen den Summanden 4s5 und σ0 den Summanden s51 bei).

  4. Schritt: Aufstellen der Gewichtsfunktion w.
    • Hier wähle etwa für Rot Gewicht R und für Blau Gewicht B und erhalte w(R,B)=1R+1B+11=R+B+1 (beispielsweise taucht 1R als Summand auf, weil es genau eine Farbe mit Gewicht R gibt, und der Summand 11 bedeutet, dass ungefärbte Perlen mit Gewicht 1 berücksichtigt werden).

  5. Schritt: Einsetzen der Gewichtsfunktion in den Zyklenzeiger.
    • Hier ergibt sich mit einer längeren Rechnung: ZG(w(R,B),w(R2,B2),w(R3,B3),w(R4,B4),w(R5,B5))=15(w(R,B)5+4w(R5,B5))=15((R+B+1)5+4(R5+B5+1))=R5+R4(B+1)+R3(2B2+4B+2)+R2(2B3+6B2+6B+2)+R1(B4+4B3+6B2+4B+1)+R0(B5+B4+2B3+2B2+B+1)
  6. Schritt: Ablesen und Aufsummieren der relevanten Koeffizienten.
    • Hier sind die Koeffizienten von RrBb mit r=2 und b1 relevant, also die von R2B3, R2B2, R2B. Ihre Summe ist 2+6+6=14.

Folglich gibt es bis auf Drehung 14 solche Ketten mit genau 2 roten und zumindest 1 blauen Perle.

1.2  Allgemeine Formulierung

Gegeben sei die Menge X={1,,n} und eine Untergruppe G der symmetrischen Gruppe Sn.

Außerdem sei F eine endliche Menge von Farben und FwNr0 eine Gewichtsfunktion. Definiere dann ein Polynom w(X1,,Xr):=k1,,krwk1,,krXk11Xkrr mit Koeffizienten wk1,,kr:=|w1(k1,,kr)| der Anzahl Farben vom Gewicht Xk11Xkrr.

Bemerkung. Im Beispiel oben war r=2 und (X1,X2)=(R,B).

Die Funktion w induziert eine Gewichtsfunktion GAbb(X,F)¯wNr0 auf der Menge der Bahnen mit der Eigenschaft ¯w(Gf)=ni=1w(f(i)). Definiere ein weiteres Polynom ¯w(X1,,Xr):=k1,,kr¯wk1,,krXk11Xkrr mit Koeffizienten ¯wk1,,kr:=|¯w1(k1,,kr)| der Anzahl Bahnen vom Gewicht Xk11Xkrr.

Satz (Pólya). Es gilt die folgende Gleichheit von Polynomen: ¯w(X1,,Xr)=ZG(w(X1,,Xr),w(X21,,X2r),,w(Xn1,,Xnr))

2  Die Platonischen Körper

Feuer Erde Luft Wasser Kosmos
 

2.1  Klassifikation der regulären Polyeder

Reguläre Polyeder sind aus regelmäßigen, zueinander kongruenten Vielecken zusammengesetzt, wobei an jeder Ecke gleich viele Flächen und gleich viele Kanten aufeinandertreffen. Gruppentheoretisch lässt sich Regularität durch folgende Symmetrieeigenschaft charakterisieren:

  • Für jedes Tripel (F,K,E) bestehend aus einer Fläche F des Polyeders, welche die Kante K mit Endeckpunkt E enthält, und für jedes andere solche Tripel (F,K,E) gibt es eine Symmetrie des dreidimensionalen Raums, die (F,K,E) auf (F,K,E) abbildet.

Satz. Bis auf Größe, Verschiebung und Drehung gibt es genau fünf reguläre Polyeder: die platonischen Körper.

von Wikipedia:
Die platonischen Körper
Tetraeder Hexaeder (Würfel) Oktaeder Dodekaeder Ikosaeder
  120px-Tetrahedron-slowturn.gif 120px-Hexahedron-slowturn.gif 120px-Octahedron-slowturn.gif 120px-Dodecahedron-slowturn.gif 120px-Icosahedron-slowturn.gif
Art der Seitenflächen gleichseitige Dreiecke Quadrate gleichseitige Dreiecke regelmäßige Fünfecke gleichseitige Dreiecke
Anzahl Seitenflächen eines Körpers 4 6 8 12 20
Anzahl Ecken eines Körpers 4 8 6 20 12
Anzahl Kanten eines Körpers 6 12 12 30 30
Anzahl Kanten in einer Körperecke 3 3 4 3 5
dual zu Tetraeder Oktaeder Hexaeder (Würfel) Ikosaeder Dodekaeder
Schläfli-Symbol {3,3} {4,3} {3,4} {5,3} {3,5}

Beweis des Satzes. Sei P ein reguläres Polyeder, das aus n-Ecken F zusammengesetzt ist, sodass an jeder Ecke E genau m Flächen aufeinandertreffen. Da die Winkel zwischen benachbarten Kanten in den regulären n-Ecken F alle gleich π2πn sind, muss gelten: m(π2πn)<2π Diese Ungleichung lässt sich umstellen zu 12<1n+1m. Es gilt natürlich n,m3. Wegen der Ungleichung muss deshalb n,m5 sein. Durchprobieren aller Möglichkeiten n,m{3,4,5} liefert folgende Lösungspaare für die Ungleichung: (n,m){(3,3),(4,3),(3,4),(5,3),(3,5)} Ein Vergleich mit (dem Schläfli-Symbol in) obiger Tabelle zeigt, dass P ein platonischer Köper sein muss.

Bemerkung. Streng genommen müsste für einen vollständigen Beweis noch gezeigt werden, dass die platonischen Körper auch tatsächlich existieren.

3  Symmetriegruppen der platonischen Körper

3.1  Dualität

Das duale Polyeder P eines Polyeders P ergibt sich, indem die Flächenmittelpunkte von P als Ecken von P gewählt und zwei Ecken von P durch eine Kante verbunden werden, wenn die zugehörigen Flächen in P eine gemeinsame Kante haben. Zweimaliges Anwenden dieser Konstruktion liefert wieder ein Polyeder "gleichen Typs" wie P, d.h. bis auf Größe, Drehung und Verschiebung gilt P=P.

Jeder platonische Körper besizt in diesem Sinne einen zugehörigen dualen platonischen Körper:

  • Das Tetraeder ist selbstdual:

  • Das Oktaeder ist dual zum Hexaeder (Würfel).


  • Das Ikosaeder ist dual zum Dodekaeder.


Duale platonische Körper haben dieselben räumlichen Symmetrien, sodass zur Bestimmung der Symmetriegruppen aler platonischen Körper nur diejenigen von Tetraeder, Würfel und Dodekaeder ermittelt werden müssen.

3.2  Symmetrien des Tetraeders

Bezeichne mit A,B,C,D die Ecken des Tetraeders (siehe Abbildung unten). Die Gruppe G aller räumlichen Symmetrien erzeugt von den Drehungen, die das Tetraeder auf sich selbst abbilden, operiert auf der Menge X={ABD,BCD,CAD,ABC}ˆ={1,2,3,4} der Flächen des Tetraeders. Dies liefert einen Gruppenhomomorphismus GS4. Er ist injektiv, weil jede Symmetrie vollständig durch ihre Wirkung auf die Flächen beschrieben wird. Auf diese Weise lässt sich G als Untergruppe von S4 auffassen, die aus folgenden Elementen besteht:

  • Insgesamt 4×2=8 Drehungen von ±120 um eine Achse durch eine Ecke und den gegenüberliegenden Flächenmittelpunkt.

    Zum Beispiel (1,2,3)S4:

  • Insgesamt 62=3 Drehungen von 180 um eine Achse durch zwei sich gegenüberliegende Kantenmittelpunkte.

    Zum Beispiel (1,4)(2,3)S4:

Zusammen mit der Identität ()S4 enthält G damit 12 Elemente. Explizit ist G={(),(1,2,3),(1,3,2),(1,2,4),(1,4,2),(1,3,4),(1,4,3),(2,3,4),(2,4,3),(1,2)(3,4),(1,3)(2,4),(1,4)(2,3)}. und der Zyklenzeiger berechnet sich somit als ZG(s1,s2,s3,s4)=112(s41+3s22+8s1s3).

Das Vorzeichen aller Elemente von G ist positiv (d.h. sgn(σ)=1 für alle σG). Somit gilt GA4. Wegen |G|=12=4!2=|A4| ist die Symmetriegruppe G des Tetraeders demzufolge die alternierende Gruppe G=A4.

Bemerkung. Die volle Symmetriegruppe H des Tetraeders, deren Erzeuger neben den Drehungen auch die räumlichen Spiegelungen sind, die das Tetraeder auf sich selbst abbilden, ist die symmetrische Gruppe S4. In der Tat zeigt die obige Argumentation ja GHS4. Wegen HG und [S4:G]=2 muss daher H=S4 gelten.

Beispiel eines Färbungsproblems. Die Anzahl der bis auf Drehung verschiedenen Möglichkeiten, die Tetraederflächen mit n Farben einzufärben, ist ZG(n,n,n,n)=112(n4+11n2). Für n=2 Farben ergeben sich also beispielsweise 16+4412=5 Färbungen.

3.3  Symmetrien von Hexaeder (Würfel) und Oktaeder

Bezeichne mit A,B,C,D,E,F,G,H die Würfelecken (siehe unten). Wie beim Tetraeder operiert die Gruppe G aller räumlichen Symmetrien erzeugt von den Drehungen, die den Würfel auf sich selbst abbilden, auf der Menge X={ADEF,BAFG,CBGH,DCHE,ABCD,EHGF}ˆ={1,2,3,4,5,6} der sechs Würfelflächen, womit sich G als Untergruppe von S6 auffassen lässt, die aus folgenden Elementen besteht:

  • Insgesamt 62×2=6 Drehungen von ±90 um eine Achse durch zwei sich gegenüberliegende Flächenmittelpunkte.

    Zum Beispiel (1,2,3,4)S6:

  • Insgesamt 62=3 Drehungen von 180 um eine Achse durch zwei sich gegenüberliegende Flächenmittelpunkte.

    Zum Beispiel (1,2,3,4)2=(1,3)(2,4)S6.

  • Insgesamt 82×2=8 Drehungen von ±120 um eine Achse durch zwei sich gegenüberliegende Ecken.

    Zum Beispiel (1,6,4)(2,3,5)S6:

  • Insgesamt 122=6 Drehungen von 180 um eine Achse durch zwei sich gegenüberliegende Kantenmittelpunkte.

    Zum Beispiel (1,6)(2,4)(3,5)S6:

Zusammen mit der Identität ()S6 enthält G damit 24 Elemente und der Zyklenzeiger ist ZG(s1,s2,s3,s4,s5,s6)=124(s61+6s32+8s23+6s21s4+3s21s22).

Bemerkung. Die Operation von G auf den vier Diagonalen des Würfels entspricht einem injektiven Gruppenhomomorphismus GS4. Wegen |G|=24=4!=|S4| ergibt sich für die Symmetriegruppe des Würfels also GS4.

Die volle Symmetriegruppe H des Würfels ist erzeugt von den Drehungen in G und den räumlichen Spiegelungen, die den Würfel auf sich selbst abbilden. Diese Spiegelungen lassen sich alle aus der Spiegelung (5,6)S6, die Ober- und Unterseite des Würfels tauscht, durch Konjugation mit Drehungen aus G erhalten. Hieraus schließlich folgt HS4×Z/2Z.

Beispiel eines Färbungsproblems. Die Anzahl der bis auf Drehung verschiedenen Färbungen der Würfelflächen mit n Farben ist ZG(n,n,n,n,n,n)=124(n6+3n4+12n3+8n2). Für n=3 Farben ergeben sich also beispielsweise 36+334+1233+83224=57 Färbungen.

3.4  Symmetrien von Dodekaeder und Ikosaeder

Die Gruppe G aller räumlichen Symmetrien erzeugt von den Drehungen, die das Dodeakeder auf sich selbst abbilden, operiert auf der Menge Xˆ={1,2,3,,12} der zwölf Flächen des Dodekaeders, womit sich G als Untergruppe von S12 auffassen lässt. Hier sei angenommen, dass 11 "die obere" Fläche und 12 "die untere" bezeichnet und außerdem die übrigen Flächen auf der "oberen Ebene" mit 1,2,3,4,5 und die auf der "unteren Ebene" mit 6,7,8,9,10 gegen den Uhrzeigersinn durchnummeriert sind, sodass 1 die Fläche "direkt über" 6 und 7 benennt. Die Elemente von G sind dann die folgenden:

  • Insgesamt 122×4=24 Drehungen von ±72 und ±144 um eine Achse durch zwei sich gegenüberliegende Flächenmittelpunkte.

    Zum Beispiel (1,2,3,4,5)(6,7,8,9,10)S12:

  • Insgesamt 202×2=20 Drehungen von ±120 um eine Achse durch zwei sich gegenüberliegende Ecken.

    Zum Beispiel (1,8,4)(2,3,11)(5,7,9)(6,12,10)S12:

  • Insgesamt 302=15 Drehungen von 180 um eine Achse durch zwei sich gegenüberliegende Kantenmittelpunkte.

    Zum Beispiel (1,9)(2,4)(3,11)(5,8)(6,12)(7,10)S12:

Zusammen mit der Identität ()S12 enthält G damit 60 Elemente und der Zyklenzeiger ist ZG(s1,s2,s3,,s12)=160(s121+15s62+20s43+24s21s25).

Bemerkung. Es gibt fünf Möglichkeiten acht Ecken des Dodekaeders zu wählen, sodass diese die Eckpunkte eines eingeschriebenen Würfels bilden:

Die Operation von G auf der Menge dieser fünf Würfel liefert einen injektiven Gruppenhomomorphismus GS5 und es folgt für die Symmetriegruppe des Dodekaeders wegen |G|=60=5!2=|A5| die Isomorphie GA5.

Mit einer ähnlichen Begründung wie oben im Fall des Würfels gegeben berechnet sich die volle Symmetriegruppe H des Dodekaeders, welche neben den Drehungen in G noch von den räumlichen Spiegelungen erzeugt wird, die das Dodekaeder auf sich selbst abbilden, damit als HA5×Z/2Z.

Beispiel eines Färbungsproblems. Die Anzahl der bis auf Drehung verschiedenen Färbungen der Dodekaederflächen mit n Farben ist ZG(n,n,n,,n)=160(n12+15n6+44n4). Für n=5 Farben ergeben sich also beispielsweise 512+1556+445460=4073375 Färbungen.

4  Klassifikation der endlichen Drehgruppen

Der folgende Satz ist interessant, weil er zeigt, dass jede endliche Gruppe, die aus Drehungen des Raums besteht, entweder die Symmetriegruppe eines platonischen Körpers ist oder aber eine der in dieser Vorlesung schon oft beispielhaft betrachteten Gruppen Z/nZ und Dn.

Satz. Jede endliche Gruppe G von Drehungen des dreidimensionalen euklidischen Raums ist eine der folgenden Gruppen:

  1. Eine zyklische Gruppe Cn mit n1, die aus den n Drehungen um eine fixierte Achse mit Winkeln 2πk/n für k{0,1,2,,n1} besteht.

  2. Eine Diedergruppe D2, die aus den vier Drehungen besteht, welche zwei fixierte orthogonale Geraden jede in sich selbst überführen.

  3. Eine Diedergruppe Dn mit n>2, die aus den 2n räumlichen Drehsymmetrien eines fixierten in einer Ebene liegenden regelmäßigen n-Ecks besteht. (Eine Spiegelung im zweidimensionalen kann im dreidimensionalen Raum als Drehung realisiert werden!)

  4. Eine Symmetriegruppe eines platonischen Körpers.

Beweis (aus einem Skript von Wolfgang Sörgel).

Für jedes vom neutralen Element verschiedene Element gG{1} unserer Gruppe definieren wir seine "Pole" als die beiden Schnittpunkte seiner Drehachse mit der Einheitssphäre. Sei P die Menge aller Pole von Elementen aus G{1}. Natürlich ist P eine endliche Menge und G operiert auf P.

Wir zählen nun die Menge M aller Paare (g,p) mit gG{1} und p einem Pol von g auf zwei Weisen: Einmal gehört jedes von 1 verschiedene Gruppenelement gG{1} zu genau zwei Polen, also haben wir |M|=2(|G|1). Andererseits gehört jeder Pol pP zu genau |Gp|1 von 1 verschiedenen Gruppenelementen, also haben wir |M|=pP(|Gp|1). Zusammen erhalten wir so die Gleichung 2(|G|1)=pP(|Gp|1). Sei nun P=P1Pr die Bahnzerlegung von P und seien piPi fest gewählt. Der Stabilisator Gpi von pi habe sagen wir ni2 Elemente. Die zugehörige Bahn hat dann |Pi|=|G|/ni Elemente, und alle Stabilisatoren zu Polen aus Pi haben auch ni Elemente. Fassen wir also die Pole jeder Bahn in unserer Summe zu einem Summanden zusammen, so können wir in unserer Gleichung die rechte Seite umformen zu ri=1(|G|/ni)(ni1) und es ergibt sich die Gleichung 22|G|=ri=1(11ni). Jeder Summand auf der rechten Seite ist mindestens 12, der Ausdruck links ist aber kleiner als 2. Es kommen also nur bis zu drei Bahnen von Polen in Betracht. Wir machen nun eine Fallunterscheidung nach der Zahl r der Bahnen von Polen.

Fall 0. Es gibt überhaupt keine Pole. In diesem Fall besteht G nur aus dem neutralen Element, und wir haben die Gruppe C1 vor uns.

Fall 1. Ganz P ist eine Bahn. Das ist unmöglich, denn es muss |G|2 gelten, wenn es überhaupt Pole geben soll, und damit hätten wir 22|G|1>11n1 im Widerspruch zu unserer Gleichung.

Fall 2. Es gibt genau zwei Bahnen P1 und P2 in P. Wir haben dann 2|G|=1n1+1n2. Da n1 und n2 Teiler sind von |G|, haben wir ni|G| und damit notwendig n1=n2=|G|. Alle Pole werden also von der Gruppe festgehalten, es gibt folglich nur zwei Pole, die sich notwendig gegenüberliegen müssen. Damit sind wir im Fall der zyklischen Gruppen Cn mit n>1.

Fall 3. Es gibt genau drei Bahnen P1, P2 und P3 in P, wir haben also 2|G|=1n1+1n2+1n31. Wir dürfen annehmen n1n2n3. Sicher gilt dann n1=2, sonst wäre die rechte Seite 0. Haben wir auch n2=2, so kann n3 beliebige Werte annehmen und wir haben |G|=2n3. Die Bahn P3 besteht dann aus zwei Polen, die sich notwendig gegenüberliegen, und die Gruppe wird eine Diedergruppe Dn3. Sicher sind (2,4,4) und (2,3,6) unmöglich für (n1,n2,n3), da 12+14+141=0=12+13+16, also bleiben nur die Fälle (2,3,3), (2,3,4) und (2,3,5), und man berechnet leicht die zugehörigen Gruppenordnungen zu 12, 24, und 60. Die Ecken des zugehörigen Tetraeders bzw. Würfels bzw. Dodekaeders sind nun genau die Elemente von P2, und wir überlassen den Rest des Beweises dem Leser.

5  Elliptische Kurven

Im Folgenden sei K ein Körper, in dem 2 und 3 multiplikativ invertierbar sind.

Zulässige Wahlen für K sind also zum Beispiel die reellen Zahlen K=R oder auch K=Z/pZ für Primzahlen p>3.

5.1  Definition

Eine elliptische Kurve ist eine ebene Kurve gegeben als Lösungsmenge

E:=Ea,b:={(x,y)K2:y2=x3+ax+b}{}

für feste Parameter a,bK mit der Eigenschaft δa,b:=4a3+27b20.

Bemerkung. Im Fall K=R der reellen Zahlen entscheidet das Vorzeichen von δa,b, ob der Graph der elliptischen Kurve Ea,b zusammenhängend ist. Bei positivem Vorzeichen ist dies der Fall und bei negativem besteht er aus zwei Komponenten.

Zum Beispiel besitzt die elliptische Kurve E1,2 den Wert δ1,2=4(1)3+2722=104>0 und hat einen zusammenhängenden Graphen:

Für die elliptische Kurve E2,1 hingegen ergibt sich δ2,1=4(2)3+2712=5<0 und der Graph besteht aus zwei Komponenten:

Bemerkung. Ist K ein endlicher Körper mit q Elementen, so besteht natürlich auch die Kurve E aus nur endlich vielen Punkten. Die Anzahl N der Punkte auf E genügt dann der sogenannten Hasse-Schranke: |N(q+1)|2q

5.2  Gruppenstruktur

Auf jeder elliptischen Kurve E=Ea,b lässt sich eine Verknüpfung + definieren, unter der E zur abelschen Gruppe wird. Diese Verknüpfung hat einen geometrischen Ursprung und lässt sich explizit folgendermaßen beschreiben:

Zunächst wird für alle Punkte P auf E P+ := P+P := P verlangt, wodurch zum neutralen Element von + wird.

Der Spiegelpunkt für von verschiedene Punkte P=(xP,yP) auf E ist der Punkt P:=(xP,yP), der sich durch Spiegelung an der x-Achse ergibt. Da y quadratisch in der E definierenden Gleichung auftaucht, liegt mit P auch P auf E.

Durch die Forderung P+(P):= wird P zum Inversen von P bezüglich +.

Schließlich setze für Punkte P=(xP,yP) und Q=(xQ,yQ) mit QP auf E

P+Q:=(s2PQxPxQ,s3PQ+(2xP+xQ)sPQyP),

wobei der Steigungsparameter sPQ zu berechnen ist als

sPQ:={yPyQxPxQfalls xPxQ,3x2P+a2yPfalls xP=xQ.

Bemerkung. Die Verknüpfung P+Q zweier Punkte P, Q auf E ist gerade so definiert, dass (P+Q) der eindeutige dritte Schnittpunkt R von E mit der Geraden durch P und Q ist:

Der Fall 1 zeigt die "generische" Situation, wo die Punkte PQ verschieden sind und die Gerade PQ keine Tangente von E ist. Die Fälle 2-4 sind in dem Sinn "entartet", dass die Gerade PQ Tangente von E in Q ist (Fall 2) bzw. der dritte Schnittpunkt im Unendlichen liegt (Fall 3) bzw. die Punkte P und Q zusammenfallen und die Tangente in diesem Punkt als einzigen weiteren Schnittpunkt mit E den Punkt besitzt (Fall 4).

In der generischen Situation funktioniert die Addition zweier Punkte P,Q auf E also wie folgt:

  1. Zeichne die Gerade durch P und Q und bestimme ihren dritten Schnittpunkt R mit E.
  2. Spiegle R an der x-Achse. Der so erhaltene Punkt ist die Summe P+Q.

Folgendes Online-Tool ermöglicht es, die Addition der Punkte interaktiv nachzuvollziehen:

Satz. Mit der Verknüpfung + wird jede elliptische Kurve E zur abelschen Gruppe.

Beweis. Folgende Eigenschaften müssen überprüft werden, worauf hier aber verzichet wird:

  • Assoziativität: (P+Q)+R=P+(Q+R) für alle Punkte P,Q,R auf E.
  • Kommutativität: P+Q=Q+P für alle Punkte P,Q auf E.
  • Existenz eines neutralen Elements: Das neutrale Element ist wegen P+=P=+P für alle Punkte P auf E.
  • Existenz von inversen Elementen: Das zu einem Punkt P=(xP,yP) auf E inverse Element ist P wegen P+(P)=.

5.3  Wiederholung: Diskreter Logarithmus

Sei G eine Gruppe. Für ein fixiertes Element g von G der Ordnung n wird die Umkehrabbildung des Gruppenisomorphismus expg:Z/nZg¯xgx als diskreter Logarithmus logg bezeichnet.

Diskrete Logarithmen finden Anwendung in der Kryptographie. Hierzu wird eine "hinreichend komplizierte" Gruppe G gewählt, für die das Berechnen der diskreten Logarithmen sehr schwierig aber das Berechnen von Potenzen einfach ist. Das heißt, bei Kenntnis von gG und hg darf dasjenige ¯xZ/nZ mit h=gx nur schwer berechenbar sein, wohingegen für gegebenes gG und xZ die Potenz gx einfach zu berechnen sein muss.

Die Elliptische-Kurven-Kryptographie macht sich die Tatsache zunutze, dass die Gruppenstruktur von geeignet gewählten elliptischen Kurven über endlichen Körpern als in diesem Sinne "hinreichend kompliziert" eingestuft wird.

Beispiel (Diffie-Hellmann-Schlüsselaustausch). Fixiere eine Gruppe G und ein Element g in G der Ordnung n.

  • Ein privater Schlüssel besteht in der Wahl einer Zahl xZ mit 0<x<n. Der zugehörige öffentliche Schlüssel ist h=gx.

Wollen zwei Parteien A und B einen geheimen, d.h. nur ihnen beiden bekannten Schlüssel k erstellen, können sie wie folgt vorgehen:

  1. Beide Parteien wählen nur ihnen selbst bekannte, private Schlüssel xA und xB.
  2. Dann berechnen und veröffentlichen sie jeweils die zugehörigen öffentlichen Schlüssel hA und hB.
  3. Als geheimer Schlüssel kann nun k=gxAxB dienen.

In der Tat kann A einerseits k=hxAB und B andererseits k=hxBA allein mit Kenntnis der öffentlichen und des jeweiligen eigenen privaten Schlüssels berechnen. Unter der Annahme, dass diskrete Logarithmen in der Gruppe G schwierig zu berechnen sind, kann der geheime Schlüssel k jedoch von Außenstehenden selbst bei Kenntnis beider öffentlicher Schlüssel hA und hB nicht leicht ermittelt werden.

Beispiel (Elgamal-Verschlüsselungsverfahren). Der im Diffie-Hellmann-Schlüsselaustausch erstellte, geheime Schlüssel k lässt sich auch direkt zum Verschlüsseln nutzen. Möchte A nämlich die Nachricht hG verschlüsselt an B schicken, funktioniert dies ganz einfach folgendermaßen:

  1. A verschlüsselt die Nachricht als l=kh.
  2. B entschlüsselt die Nachricht als h=k1l.

Bemerkung (siehe NIST.FIPS.DSS für Details). Typischerweise werden in kryptographischen Anwendungen elliptische Kurven Ea,b über endlichen Körpern K=Z/pZ mit einem fixierten Element gEa,b der Ordnung n durch ihre sogenannten domain parameter (p,a,b,g,n,m) angegeben, wobei m den Index der Untergruppe g bezeichnet. In der Praxis verwendet werden Parameter mit folgenden Eigenschaften:

  • p ist eine Primzahl größer 21911058.
  • a=3 "for efficiency" und b "pseudo-randomly" gewählt.
  • g ist ein beliebiger Punkt der Ordnung n.
  • n ist eine Primzahl mit ungefähr gleicher Bit-Länge wie p.
  • m ist möglichst klein.

Üblicherweise gilt für die Bit-Länge log2(p){192,224,256,384,521} und für den Index m{1,2,4}.

Das Security-Level bei solcher Wahl der domain parameter wird aktuell als 12log2(p)-bit angesetzt. Alle die Sicherheit betreffenden Aussagen sollten aber natürlich stets mit Vorsicht genossen werden, zum Beispiel wegen möglicher Einflussnahme der NSA.