Veranstaltung:

Proseminar Elementare Zahlentheorie und Kryptologie, VAK 03115,

SoSe 2006

Elementare Theorie El iptischer Kurven

Verfasser:

Volker Irmler

Studiengang:

Mathematik (Diplom), 2. Semester

---

Elementare Theorie El iptischer Kurven

1.Einleitung

Die vorliegende Ausarbeitung über El iptische Kurven ist im Rahmen meines Vortrags

im Proseminar Elementare Zahlentheorie und Kryptologie enstanden. Ihr Ziel ist es,

einen ersten, kurzen Einblick in die Theorie El iptischer Kurven zu geben. Dabei wird

der Verdeutlichung der wesentlichen Eigenschaften und Fragestel ungen der Vorzug

vor einer möglichst ausführlichen, in die Tiefe gehenden Darstel ung der Theorie

gegeben. Zu diesem Zweck sind zahlreiche Beispiele enthalten.

Zunächst wird der Begrif der El iptischen 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 El iptischen Kurven über endlichen Körpern,

insbesondere ihrer Elementezahl und Gruppenstruktur.

2.Begriffsbestimmung
Definition 1a)

Sei K ein Körper mit char K 2,3 , x3axb mit a ,b K

ein Polynom 3. Grades ohne vielfache Nul stel en.

Dann heißt die Menge

{ x , y K ×K y2=x3axb } {0}

(1)

el iptische 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 Nul stel en, wenn

seine Diskrimante Nul ist. Die Diskriminate eines Polynoms der Form x3axb

ist gleich 4a327b2 .

Definition 1b)

Sei K ein Körper mit char K =2 , x3axb mit a ,b K ein

Polynom 3. Grades.

Dann heißt

{ x , y K ×K y2y=x3axb } {0}

(2)

el iptische Kurve über K .

Seite 2 von 12

---

Elementare Theorie El iptischer Kurven

Definition 1c)

Sei K ein Körper mit char K =3 , x3ax2bxc mit

a ,b K ein Polynom 3. Grades ohne vielfache Nul stel en.

Dann heißt

{ x , y K ×K y2=x3ax2bxc } {0}

(3)

el iptische Kurve über K .

Beispiel 1

{x ,y × y2=x3-x } {0} ist eine El iptische Kurve über

dem Körper der reel en Zahlen (welcher ja Charakteristik 0 besitzt), da die

Diskrimante des Polynoms auf der rechten Seite der Gleichung

4

3

-1 2702=-40 ist und damit dieses Polynom keine vielfachen Nul stel en

besitzt.

Der Graph dieser El iptischen Kurve sieht über [-2,2]×[-2,2] wie folgt aus:

Man sieht sofort, dass die Kurve symmetrisch zur xAchse ist.

3.Addition auf El iptischen Kurven

Als motivierendes und anschauliches Beispiel sol uns zunächst die Addition auf

El iptischen Kurven über den reel en Zahlen dienen.

In diesem Kapitel sei E eine durch y2 = x3 ax b definierte El iptische Kurve

über .

Definition 2

Sei P = x y

1, 1 E {0} . Dann definieren wir -P als

x1,- y1 .

-0 definieren wir als 0 .

Seite 3 von 12

---

Elementare Theorie El iptischer Kurven

Bemerkung 1

Da für x , y

2

aus y2 = x3 ax b

-y = x3 ax b

folgt, folgt aus P E

-P E .

Definition 3

Seien P = x y

y

.

1, 1 , Q = x2, 2 E {0} mit x1 x 2

Sei g die durch P und Q definierte Gerade.

Wir definieren S als 3. Schnit punkt von g mit dem Graph von E .

Die Summe PQ wird definiert als -S .

Als Veranschaulichung dient uns

Beispiel 2

Auf der hier dargestel ten, durch y2 = x3-2x3 definierten El iptischen Kurve

werden die Punkte P und Q addiert. Dazu ermit elt man zunächst den

Schnit punkt 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 y

1, 1 E {0} mit y1 0 .Sei g die Tangente an

E im Punkt P .

Wir definieren S als einzigen anderer Schnit punkt von g mit dem Graph von

E . PP wird definiert als -S .

Als Il ustration dieses Fal s dient uns

Beispiel 3

Seite 4 von 12

---

Elementare Theorie El iptischer Kurven

Hier wird auf derselben Kurven wie in Beispiel 2 der Punkt P zu sich selbst

addiert. Dazu ermit elt man die Tangente an der el iptischen Kurve in diesem Punkt.

Es existiert genau ein weiterer Schnit punkt 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

0 .

P0 definieren wir genauso wie 0 P als P und schließlich setzen wir

00=0 .

Bemerkung 2

Im Fal Q = -P schneidet die Gerade durch P und Q , die

paral el zur yAchse verläuft, den Graphen der Kurve in keinem weiteren Punkt. Nun

stel t man sich vor, dass diese Gerade einen Punkt, der sich ,,unendlich weit oben"

befindet, trif t. Dieser Punkt ist der Punkt im Unendlichen, 0 .

Wir haben noch zu zeigen, dass der Schnit punkt 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

Schnit punkt

S=x y

3, 3

von

g mit

E . Dabei sind

y

2

y

x

2- y1

2- y1

3 = x

- x1 -x2 , y3 =

x

x

3- x1 y1 .

2- x1

2- x1

b) Seien P ,g wie in Definition 4. Dann existiert genau ein weiterer

Schnit punkt

S=x y

3, 3 von

g mit

E . Dabei sind

3x2

2

3x2

x

1-a

1a

3 =

2y -2x1 , y3 = 2y x3-x1 y1 .

1

1

Beweis

zu a) g wird durch die Gleichung y= x dargestel t, da g aufgrund von

x

nicht paral el zur yAchse verläuft. Of enbar sind

1 x 2

= y2- y1/ x2-x1

und = y

.

1- x1

Ein Punkt

2

r , s

ist genau dann Schnit punkt von g und E , wenn r

und s eine Lösung des folgenden Gleichungssystems in x und y sind.

y = x

(4)

y2 = x3axb

(5)

Seite 5 von 12

---

Elementare Theorie El iptischer Kurven

Dessen Lösungen erhalten wir, indem wir (4) in (5) einsetzen, wir erhalten:

2

x = x3ax b

und formen um zu

x3

2

2

- x2 a- 2 xb- = 0 .

Exkurs

Seien f K [ X ] ein normiertes Polynom 3. Grades, seien 1, 2, 3,

Nul stel en von f . Dann lässt sich f of enbar darstel en als

X - 1 X - 2 X - 3 . Multipliziert man aus, so erhält man

f =X3 - 1 2 3 X2 ... .

Weiterhin hat ein Polynom 3 Grades f K [ X ] (Vielfachheiten mitgezählt)

entweder 0, 1 oder 3 Nul stel en.

Wir wissen: Die xKoordinaten x und x von P und Q sind Nul stel en, weil

1

2

diese Punkte sowohl auf der Kurve als auch auf der Geraden liegen.

Also ergibt sich gemäß unserem Exkurs:

2

2

= x

, also x

. Damit ist gezeigt, dass es genau einen

1 x2 x3

3= - x1- x2

weiteren Schnit punkt von g mit E gibt, dessen yKoordninate y erhalten wir

3

durch einsetzen von x in (4).

3

dy

zu b) Die Steigung der Geraden g ist in diesem Fal die Ableitung

in P.

dx

3x2a

Indem man die Gleichung der Kurve implizit ableitet, erhält man

1

=

.Der

2 y1

Rest des Beweises ist analog zu a). Die einzige Ausnahme stel t dar, dass

x

2

3 = -2x1 ist, da x

of enbar doppelte Nul stel e ist. q.e.d.

1

Bemerkung 3

Of enbar ergibt sich jetzt als Ergebnis für PQ bzw. PP

x ,

3 - y3 .

Satz 2

Eine El iptische 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

---

Elementare Theorie El iptischer Kurven

Zu a) Seien P ,Q E .

Fal 1, P = 0 :Nach Definition 5 ist P Q = Q und damit Element von E .

Fal 2, P ,Q0 und P = -Q : Nach Definition 5 ist P Q = 0 und damit

Element von E .

Fal 3, P ,Q0 mit P=x y

y

.

1, 1 , Q= x2, 2 und x1 x 2

Nach Satz 1 ist der in Definition 3 erklärte Schnit punkt S Element der Kurve, also

auch -S = P Q .

Fal 4, P ,Q0 mit P=x y

1, 1 , y1 0 und P=Q .

Nach Satz 1 ist der in Definition 4 erklärte Schnit punkt 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 .

Fal 1, P = 0 : Nach Definition ist 0 Q = Q = Q 0 .

Fal 2, P ,Q0 und P = -Q : Aus P = -Q folgt -P = Q .

Also gilt nach Definition 5: P Q = 0 = Q P

Fal 3, P ,Q 0 mit P=x y

y

:

1, 1 , Q= x2, 2 und x1 x 2

Da die Gerade durch P und Q gleich der Geraden durch Q und P ist, ist

der in Definition 3 erklärte Schnit punkt S in beiden Fäl en gleich, also auch

-S = P Q .

Fal 4, P = Q : Trivial.

Zu d) Sei P E

Nach Definition 5 gilt P0=P , folglich ist 0 das neutrale Element der

El iptischen Kurve.

Zu e) Sei P E

Fal 1, P 0 : Nach Definition 5 gilt P -P = 0 .

Fal 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 El iptischen Kurven über jedem anderen

Körper mit Charakteristik ungleich 2,3 in sinnvol er 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 El iptischen Kurve ist.

Seite 7 von 12

---

Elementare Theorie El iptischer Kurven

Die Formeln für die Addition sind im reel en Fal 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 Dif erentialrechnung 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 El iptische 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 El iptische Kurven über beliebigen

Körpern zu einer abelschen Gruppe machen

4.El iptische Kurven über endlichen

Körpern

In diesem Kapitel sei GFq ein endlicher Körper mit q Elementen.

Wir beginnen mit dem instruktiven

Beispiel 4

der durch y2 = x3 3x 4 mit

x , y definierten El iptische Kurve über

:

7

7

Ihre Punkte kann man of enbar ermit eln, indem man für jedes x

7

f x = x3 3x 4 berechnet und prüft, ob es eine Quadratwurzel y zu

7

f x gibt. Ist dies der Fal , so liegt x , y auf der Kurve. Da in jedem Körper

2

-y = y2 gilt, liegt auch x ,-y auf der Kurve. Der Punkt im Unendlichen ist

ja auf jeden Fal enthalten.

Also wird man keine El iptische Kurve über finden, die mehr als 2

7

7 1

Elemente besitzt

Seite 8 von 12

---

Elementare Theorie El iptischer Kurven

Fragt man nun nach der Elementezahl N einer El iptischen Kurve über dem Körper

GFq , so liefert uns die gerade angestel te Betrachtung folgende Abschätzung:

N 2q 1 .

Al erdings würde man vermuten, dass Nq ist, da in der multiplikativen Gruppe

eines endlichen Körpers nur die Hälfte der Elemente Quadratwurzeln besitzt. (Wir

folgen der Vorstel ung, dass die von f x = x3 ax b getrof enen

Körperelemente zufäl ig sind).

Bei der Untersuchung dieser Vermutung helfen sol

Definition 6

Sei GFq ein Körper mit q Elementen, GF*q die

multiplikative Gruppe dieses Körpers. Der quadratische Charakter von

x GF*q ist wie folgt definiert:

x = { 1, falls yGF*q:y2=x .

-1, falls yGF* q: y2x

Für x=0 definiert man x=0 .

Wir könnn nun N präzise angeben:

N = 1 1x3 ax b = q 1 x3 ax b .

x GFq

xGF q

Man kann zeigen, dass x3 ax b durch 2q beschränkt ist, das

xGFq

Resultat ist

Satz 3

(Satz von Hasse) Sei N die Elementezahl einer El iptischen Kurve über

GFq . Dann gilt: N - q 1 2q .

Einen Beweis dieses Satzes findet man z.B. in [5]

Nachdem die Frage der Elementezahl nun beantwortet ist, stel t sich als nächstes die

Frage nach der Struktur der abelschen Gruppe einer El iptischen Kurve über einem

endlichen Körper.

Dazu

Beispiel 5

Seite 9 von 12

---

Elementare Theorie El iptischer Kurven

Zu sehen ist die durch y2 = x3 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

dargestel t). Folglich ist die Gruppe zyklisch.

Es stel t sich jedoch heraus, dass dies nicht bei jeder El iptischen Kurve über einem

endlichen Körper der Fal ist. Jedoch ist die Gruppe einer El iptischen Kurve über

einem endlichen Körper in jedem Fal das Produkt zweier zyklischer Gruppen

(genauer gesagt ist sie isomorph zu einem Produkt der Form /m ×/n ).

Beispiel 6

Anhand der folgenden Verknüpfungstabel e der durch y2 = x3 x

gegebenen Kurve über sieht man, dass ihre Gruppe nicht zyklisch ist, da jedes

5

Element zu sich selbst invers ist. Gegenübergestel t ist die Verknüpfungstabel e von

/ 2 ×/ 2 , die Isomorphie fäl t sofort ins Auge.

Verknüpfungstabel e der Kurve

+

(0)

(0,0)

(2,0)

(3,0)

(0)

(0)

(0,0)

(2,0)

(3,0)

(0,0)

(0,0)

(0)

(3,0)

(2,0)

(2,0)

(2,0)

(3,0)

(0)

(0,0)

(3,0)

(3,0)

(2,0)

(0,0)

(0)

Verknüpfungstabel e von /2×/2

+

(0,0)

(1,0)

(0,1)

(1,1)

(0,0)

(0,0)

(1,0)

(0,1)

(1,1)

(1,0)

(1,0)

(0,0)

(1,1)

(0,1)

(0,1)

(0,1)

(1,1)

(0,0)

(1,0)

(1,1)

(1,1)

(0,1)

(1,0)

(0,0)

Seite 10 von 12

---

Elementare Theorie El iptischer Kurven

Wenn eine El iptische Kurve über GFq definiert ist, ist sie ja auch über dem

Erweiterungskörper GFqr , r definiert.

Die Frage lautet nun: Wenn man die Elementezahl der Kurve über GFq kennt,

kennt man dann auch ihre Elementezahl über GF qr ?

Die Antwort liefert

Satz 4

Sei E eine el iptische Kurve über GFq .Die Elementezahl N von E über

GFq sei bekannt.Dann ist es möglich die Elementezahl Nr von E über

GFqr wie folgt auszurechnen:

1. Man ermit le diejenigen komplexen Zahlen , ,für welche gilt

=

, , = q und N = q 1 .

2. Man berechne nun N

r

r .

r = qr 1 - -

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 y2 = x3 3x 4 gegebene Kurve über 7 GF 7 aus

Beispiel 4 besitzt 10 Elemente. Wir wol en nun ihre Elementezahl über GF 743

bestimmen.

Dazu suchen wir eine komplexe Zahl mit = q für die gilt:

10 = 7 1 - - = 7 1 - 2Re . Also ist Re = -1 .

Of enbar ist Im

2

= 7 - -1 = 6 .

Also gilt für die Elementezahl N

über

43

GF 743 :

N

43

43

43=7431--1i 6 --1-i 6 = 2183814375991796601528255975704057110

Seite 11 von 12

---

Elementare Theorie El iptischer Kurven

5.Literaturverzeichnis

5.1.Quellen

[1] Koblitz, N., 1987, A course in Number Theory an Cryptography, New York.

Die Visualisierungen der El iptischen Kurven wurden mit Hilfe der auf

ht p:/ www.el iptischekurven.de erhältlichen JavaApplets erstel t.

5.2.Literatur

[2] Fulton, W., 1969, Algebraic Curves, New York

[3] Koblitz, N., 1984, Introduction to El iptic Curves and Modular Forms, New York

[4] Lang, S., 1978, El iptic Curves: Diophantine Analysis, New York

[5] Silverman, J., 1986, The Arithmetic of El iptic Curves, New York

Seite 12 von 12

---