Die vorliegende Ausarbeitung über Elliptische Kurven ist im Rahmen meines Vortrags im Proseminar Elementare Zahlentheorie und Kryptologie enstanden. Ihr Ziel ist es, einen ersten, kurzen Einblick in die Theorie Elliptischer Kurven zu geben. Dabei wird der Verdeutlichung der wesentlichen Eigenschaften und Fragestellungen der Vorzug vor einer möglichst ausführlichen, in die Tiefe gehenden Darstellung der Theorie gegeben. Zu diesem Zweck sind zahlreiche Beispiele enthalten.
Zunächst wird der Begriff der Elliptischen Kurve bestimmt und im Anschluss eine Addition auf ihr erklärt, welche diese Kurven zu einer abelschen Gruppe macht. Das Kapitel 4 widmet sich schließlich Elliptischen Kurven über endlichen Körpern,
insbesondere ihrer Elementezahl und Gruppenstruktur.
Page 1
Page 2
Elementare Theorie Elliptischer Kurven
1. Einleitung
Die vorliegende Ausarbeitung über Elliptische Kurven ist im Rahmen meines Vortrags im Proseminar Elementare Zahlentheorie und Kryptologie enstanden. Ihr Ziel ist es, einen ersten, kurzen Einblick in die Theorie Elliptischer Kurven zu geben. Dabei wird der Verdeutlichung der wesentlichen Eigenschaften und Fragestellungen der Vorzug vor einer möglichst ausführlichen, in die Tiefe gehenden Darstellung der Theorie gegeben. Zu diesem Zweck sind zahlreiche Beispiele enthalten.
Zunächst wird der Begriff der Elliptischen Kurve bestimmt und im Anschluss eine Addition auf ihr erklärt, welche diese Kurven zu einer abelschen Gruppe macht. Das Kapitel 4 widmet sich schließlich Elliptischen Kurven über endlichen Körpern, insbesondere ihrer Elementezahl und Gruppenstruktur.
2.Begriffsbestimmung
Definition 1a) Sei K ein Körper mit char K ≠2,3 , x 3 axb mit a , b ∈ K ein Polynom 3. Grades ohne vielfache Nullstellen. Dann heißt die Menge
{ x , y ∈ K ×K ∣ y 2 =x 3 axb } ∪ {0} (1)
elliptische Kurve über K .
Dabei heißt O Punkt im Unendlichen, auf seine Bedeutung wird in Kapitel 3 eingegangen.
Erinnerung Ein normiertes Polynom besitzt genau dann vielfache Nullstellen, wenn seine Diskrimante Null ist. Die Diskriminate eines Polynoms der Form x 3 axb ist gleich 4a 3 27b 2 .
Definition 1b) Sei K ein Körper mit char K =2 , x 3 axb mit a , b ∈ K ein Polynom 3. Grades. Dann heißt
{ x , y ∈ K ×K ∣ y 2 y=x 3 axb } ∪ {0} (2)
elliptische Kurve über K .
Seite 2 von 12
Page 3
Elementare Theorie Elliptischer Kurven
Definition 1c)
Sei
K
ein Körper mit
char K
=3
,
x
Dann heißt
{ x , y ∈ K ×K ∣ y 2 =x 3 ax 2 bxc } ∪ {0} (3)
elliptische Kurve über K .
Beispiel 1 { x , y ∈ ℝ×ℝ ∣ y 3 −x } ∪ {0 } ist eine Elliptische Kurve über 2 =x
dem Körper der reellen Zahlen (welcher ja Charakteristik 0 besitzt), da die Diskrimante des Polynoms auf der rechten Seite der Gleichung 4⋅−1 3 27⋅0 2 =−4≠0 ist und damit dieses Polynom keine vielfachen Nullstellen besitzt.
Der Graph dieser Elliptischen Kurve sieht über [−2,2 ]×[−2,2 ] wie folgt aus:
Man sieht sofort, dass die Kurve symmetrisch zur xAchse ist.
3.Addition auf Elliptischen Kurven
Als motivierendes und anschauliches Beispiel soll uns zunächst die Addition auf Elliptischen Kurven über den reellen Zahlen dienen. In diesem Kapitel sei E eine durch y 3 ax b definierte Elliptische Kurve 2 = x über ℝ .
Definition 2
Sei
P
=
x
1,
y
1
∈
E
∖ {0}
. Dann definieren wir
−P
als
Seite 3 von 12
Page 4
Elementare Theorie Elliptischer Kurven
Bemerkung 1
Da für
x , y
∈ ℝ
aus
y
folgt, folgt aus P ∈ E −P ∈ E .
Definition 3 Seien
P
=
x
1,
y
1
, Q
=
x
2,
y
2
∈
E
∖ {0}
mit
x
1
≠x
2
. Sei
g
die durch
P
und
Q
definierte Gerade. Wir definieren
S
als 3. Schnittpunkt von
g
mit dem Graph von
E
. Die Summe
PQ
wird definiert als
−S
. Als Veranschaulichung dient uns
Beispiel 2
Auf der hier dargestellten, durch y 2 = x 3 −2x3 definierten Elliptischen Kurve werden die Punkte P und Q addiert. Dazu ermittelt man zunächst den Schnittpunkt S der Geraden durch P und Q mit der Kurve. Das Ergebnis der Addition erhält man, wenn man S an der xAchse spiegelt.
Definition 4 Sei P = x 1, y 1 ∈ E ∖ {0} mit y 1 ≠ 0 .Sei g die Tangente an
Wir definieren S als einzigen anderer Schnittpunkt von g mit dem Graph von
Als Illustration dieses Falls dient uns Beispiel 3
Seite 4 von 12
Page 5
Elementare Theorie Elliptischer Kurven
Hier wird auf derselben Kurven wie in Beispiel 2 der Punkt
P
zu sich selbst addiert. Dazu ermittelt man die Tangente an der elliptischen Kurve in diesem Punkt. Es existiert genau ein weiterer Schnittpunkt
S
dieser Tangente mit der Kurve.
PP erhält man schließlich, wenn man S an der xAchse spiegelt.
Definition 5 Seien
P , Q
∈
E
∖ {0}
mit
Q=−P
.
PQ
wird definiert als
P0 definieren wir genauso wie 0 P als P und schließlich setzen wir
Bemerkung 2 Im Fall Q = −P schneidet die Gerade durch P und Q , die parallel zur yAchse verläuft, den Graphen der Kurve in keinem weiteren Punkt. Nun stellt man sich vor, dass diese Gerade einen Punkt, der sich „unendlich weit oben“ befindet, trifft. Dieser Punkt ist der Punkt im Unendlichen, 0 .
Wir haben noch zu zeigen, dass der Schnittpunkt S aus Definition 3 und Definition 4 tatsächlich existiert und eindeutig bestimmt ist. Die geschieht in Satz 1
a) Seien
P ,Q , g
wie in Definition 3. Dann existiert genau ein weiterer
Schnittpunkt
b) Seien P , g wie in Definition 4. Dann existiert genau ein weiterer Schnittpunkt
Beweis
zu a)
g
wird durch die Gleichung
y= x
dargestellt, da
g
aufgrund von
und = y 1 − x 1 .
Ein Punkt r , s ∈ ℝ 2 ist genau dann Schnittpunkt von g und E , wenn r und s eine Lösung des folgenden Gleichungssystems in x und y sind.
Seite 5 von 12
Page 6
Elementare Theorie Elliptischer Kurven
Dessen Lösungen erhalten wir, indem wir (4) in (5) einsetzen, wir erhalten:
und formen um zu x 3 − 2 x 2 a−2 xb− 2 = 0 .
Exkurs
Seien
f
∈
K
[
X
]
ein normiertes Polynom 3. Grades, seien
1,
2,
3,
Nullstellen von
f
. Dann lässt sich
f
offenbar darstellen als
Weiterhin hat ein Polynom 3 Grades f ∈ K [ X ] (Vielfachheiten mitgezählt) entweder 0, 1 oder 3 Nullstellen.
Wir wissen: Die xKoordinaten x 1 und x 2 von P und Q sind Nullstellen, weil diese Punkte sowohl auf der Kurve als auch auf der Geraden liegen. Also ergibt sich gemäß unserem Exkurs:
weiteren Schnittpunkt von g mit E gibt, dessen yKoordninate y 3 erhalten wir durch einsetzen von x 3 in (4).
zu b) Die Steigung der Geraden g ist in diesem Fall die Ableitung
Indem man die Gleichung der Kurve implizit ableitet, erhält man =
Rest des Beweises ist analog zu a). Die einzige Ausnahme stellt dar, dass x 3 = 2 −2x 1 ist, da x 1 offenbar doppelte Nullstelle ist. q.e.d.
Bemerkung 3
Offenbar ergibt sich jetzt als Ergebnis für PQ bzw. PP x 3 ,− y 3 .
Satz 2 Eine Elliptische Kurve E ueber ℝ ist zusammen mit der in Definition 35 erklärten Addition eine abelsche Gruppe Zu zeigen:
a) Abgeschlossenheit der Addition
b) Assoziativität
c) Kommutativität
d) Existenz des neutralen Elements
e) Existenz inverser Elemente
Seite 6 von 12
Page 7
Elementare Theorie Elliptischer Kurven
Zu a) Seien
P ,Q
∈
E
.
Fall 1, P = 0 :Nach Definition 5 ist P Q = Q und damit Element von E . Fall 2, P ,Q≠0 und P = −Q : Nach Definition 5 ist P Q = 0 und damit Element von E .
Fall 3, P ,Q≠ 0 mit P= x 1, y 1 , Q= x 2, y 2 und x 1 ≠x 2 . Nach Satz 1 ist der in Definition 3 erklärte Schnittpunkt S Element der Kurve, also auch −S = P Q .
Fall 4, P ,Q≠ 0 mit P= x 1, y 1 , y 1 ≠ 0 und P=Q .
Nach Satz 1 ist der in Definition 4 erklärte Schnittpunkt S Element der Kurve, also auch −S = P Q .
Zu b) Der Nachweis der Assoziativität würde den Rahmen dieser Ausarbeitung sprengen, es wird auf [2], [3], [4] verwiesen.
Zu c) Seien
P ,Q
∈
E
.
Fall 1, P = 0 : Nach Definition ist 0 Q = Q = Q 0 . Fall 2, P ,Q≠0 und P = −Q : Aus P = −Q folgt −P = Q . Also gilt nach Definition 5: P Q = 0 = Q P Fall 3, P ,Q ≠ 0 mit P= x 1, y 1 , Q= x 2, y 2 und x 1 ≠x 2 : Da die Gerade durch P und Q gleich der Geraden durch Q und P ist, ist der in Definition 3 erklärte Schnittpunkt S in beiden Fällen gleich, also auch
Fall 4, P = Q : Trivial.
Zu d) Sei
P
∈
E
Nach Definition 5 gilt P0 =P , folglich ist 0 das neutrale Element der Elliptischen Kurve.
Zu e) Sei
P
∈
E
Fall 1, P ≠ 0 : Nach Definition 5 gilt P −P = 0 .
Fall 2, P = 0 : 0 als neutrales Element ist trivialerweise das inverse Element zu sich selbst. q.e.d.
Die Formeln aus Satz 1 definieren auch auf Elliptischen Kurven über jedem anderen Körper mit Charakteristik ungleich 2,3 in sinnvoller Weise eine Addition. Dazu folgende Plausibilitätsbetrachtung:
Wesentlich ist ja, dass der Punkt, den man durch Anwendung der Additionsformeln erhält, selbst wieder ein Punkt auf der Elliptischen Kurve ist.
Seite 7 von 12
Page 8
Elementare Theorie Elliptischer Kurven
Die Formeln für die Addition sind im reellen Fall dadurch entstanden, indem wir nach weiteren Lösungen der Gleichungen (4) und (5) gesucht haben. Wie wir auf (4) und (5) gekommen sind (z.B. durch Differentialrechnung wie bei der Addition eines Punktes zu sich selbst) ist ja nicht ausschlaggebend. Wichtig ist, dass die Lösungen von (4) und (5) Punkte auf der Kurve sind.
Um zu zeigen, dass es genau eine weitere Lösung gibt und zum Ausrechnen dieser Lösung haben wir als einzige Eigenschaft von ℝ benutzt, dass ℝ ein Körper ist.
Für Elliptische Kurven über Körpern der Charakteristik 2 oder 3 leitet man sich, von den Gleichungen (2) und (3) ausgehend, ähnliche Formeln wie in Satz 1 her.
Man kann zeigen, dass diese Additionsformeln Elliptische Kurven über beliebigen Körpern zu einer abelschen Gruppe machen
4.Elliptische Kurven über endlichen
Körpern
In diesem Kapitel sei GF q ein endlicher Körper mit q Elementen.
Wir beginnen mit dem instruktiven Beispiel
4
der durch
y
2
=
x
3
3x
4
mit
Ihre Punkte kann man offenbar ermitteln, indem man für jedes x ∈ ℤ 7
ja auf jeden Fall enthalten.
Also wird man keine Elliptische Kurve über ℤ 7 finden, die mehr als 2⋅7 1 Elemente besitzt
Seite 8 von 12
Page 9
Elementare Theorie Elliptischer Kurven
Fragt man nun nach der Elementezahl
N
einer Elliptischen Kurve über dem Körper
GF q , so liefert uns die gerade angestellte Betrachtung folgende Abschätzung:
Allerdings würde man vermuten, dass N≈q ist, da in der multiplikativen Gruppe eines endlichen Körpers nur die Hälfte der Elemente Quadratwurzeln besitzt. (Wir folgen der Vorstellung, dass die von f x = x 3 ax b getroffenen Körperelemente zufällig sind). Bei der Untersuchung dieser Vermutung helfen soll
Definition 6 Sei GF q ein Körper mit q Elementen, GF * q die
multiplikative Gruppe dieses Körpers. Der quadratische Charakter von
Für x=0 definiert man x =0 .
Wir könnn nun
N
präzise angeben:
Man kann zeigen, dass ∑
Resultat ist
Satz 3
(Satz von Hasse) Sei
N
die Elementezahl einer Elliptischen Kurve über
Einen Beweis dieses Satzes findet man z.B. in [5]
Nachdem die Frage der Elementezahl nun beantwortet ist, stellt sich als nächstes die Frage nach der Struktur der abelschen Gruppe einer Elliptischen Kurve über einem endlichen Körper. Dazu Beispiel 5
Seite 9 von 12
Page 10
Elementare Theorie Elliptischer Kurven
Zu sehen ist die durch
y
2
=
x
3
3x
2
gegebene Kurve über
ℤ
5
. Man sieht, dass
P=1,1
erzeugendes Element der Gruppe dieser Kurve ist, da seine Vielfachen sämtliche Elemente der Gruppe durchlaufen (
5P
= 0
ist nicht dargestellt). Folglich ist die Gruppe zyklisch.
Es stellt sich jedoch heraus, dass dies nicht bei jeder Elliptischen Kurve über einem endlichen Körper der Fall ist. Jedoch ist die Gruppe einer Elliptischen Kurve über einem endlichen Körper in jedem Fall das Produkt zweier zyklischer Gruppen (genauer gesagt ist sie isomorph zu einem Produkt der Form ℤ /m ℤ×ℤ/n ℤ ).
Beispiel 6
Anhand der folgenden Verknüpfungstabelle der durch
y
2
=
x
3
x
gegebenen Kurve über ℤ 5 sieht man, dass ihre Gruppe nicht zyklisch ist, da jedes Element zu sich selbst invers ist. Gegenübergestellt ist die Verknüpfungstabelle von
ℤ /2 ℤ×ℤ/2 ℤ
, die Isomorphie fällt sofort ins Auge.
Verknüpfungstabelle der Kurve
Seite 10 von 12
Page 11
Elementare Theorie Elliptischer Kurven
Wenn eine Elliptische Kurve
über
GF
q
definiert ist, ist sie ja auch
über
dem
Erweiterungskörper GF q
Die Frage lautet nun: Wenn man die Elementezahl der Kurve über GF q kennt, kennt man dann auch ihre Elementezahl über GF q Die Antwort liefert Satz 4
Sei
E
eine elliptische Kurve über
GF
q
.Die Elementezahl
N
von
E
über
In [1] ist erläutert, wie dieser Satz aus der inzwischen bewiesenen Weilschen Vermutung folgt. Für einen Beweis der Weilschen Vermutung wird auf [5] verwiesen.
Wir demonstrieren das Verfahren aus Satz 4 am
Beispiel 7 Die durch
y
2
=
x
3
3x
4
gegebene Kurve über
ℤ
7
≃
GF
7
aus
Beispiel 4 besitzt 10 Elemente. Wir wollen nun ihre Elementezahl über GF 7 bestimmen.
Dazu suchen wir eine komplexe Zahl
mit
∣∣ =
q
für die gilt:
Offenbar ist Im = 7 − −1 2 = 6 . Also gilt für die Elementezahl N 43 über GF 7
Seite 11 von 12
Page 12
Elementare Theorie Elliptischer Kurven
5.Literaturverzeichnis
5.1.Quellen
[1] Koblitz, N., 1987, A course in Number Theory an Cryptography, New York.
Die Visualisierungen der Elliptischen Kurven wurden mit Hilfe der auf http://www.elliptischekurven.de erhältlichen JavaApplets erstellt.
5.2.Literatur
[2] Fulton, W., 1969, Algebraic Curves, New York
[3] Koblitz, N., 1984, Introduction to Elliptic Curves and Modular Forms, New York [4] Lang, S., 1978, Elliptic Curves: Diophantine Analysis, New York [5] Silverman, J., 1986, The Arithmetic of Elliptic Curves, New York
Seite 12 von 12
- Arbeit zitieren
- Volker Irmler (Autor:in), 2006, Elliptische Kurven - Elementare Theorie derselben, München, GRIN Verlag, https://www.hausarbeiten.de/document/110931
