Elliptische Kurve

Elliptische Kurve

In der Mathematik ist eine elliptische Kurve eine singularitätenfreie algebraische Kurve der Ordnung 3 in der projektiven Ebene.

Beispiel einer elliptischen Kurve über dem Körper der reellen Zahlen

Elliptische Kurven über dem Körper der reellen Zahlen können als die Menge aller Punkte (x,y) \in \mathbb{R}^2 angesehen werden, die die Gleichung

y^2 = x^3 + ax + b \,

erfüllen. Die (reellen) Koeffizienten a und b müssen dabei die Bedingung 4a^3 + 27b^2 \neq 0 erfüllen (um Singularitäten auszuschließen). Im Allgemeinen wird man sich bei der Betrachtung der angegebenen Gleichung aber nicht auf den Fall reeller Koeffizienten und Lösungen beschränken, sondern vielmehr den Fall betrachten, dass Koeffizienten und Lösungen aus einem beliebigen Körper stammen. Interessant sind hierbei insbesondere die Körper der komplexen und der rationalen Zahlen sowie endliche Körper und die Frage, welche Beziehungen zwischen elliptischen Kurven bestehen, bei denen die gleiche Formel über verschiedene Körper interpretiert wird.

Elliptische Kurven sind für die Mathematik von Bedeutung, da mit ihrer Hilfe Verbindungen zwischen unterschiedlichen Bereichen der Mathematik geschaffen werden konnten. Der Mathematiker Andrew Wiles bewies im Jahre 1994 den Modularitätssatz, aus dem das bekannte zahlentheoretischen Problem des großen fermatschen Satzes gefolgert werden konnte. Praktische Anwendung finden elliptische Kurven in einigen modernen Verschlüsselungsverfahren (Elliptische-Kurven-Kryptosystem), da mit ihrer Hilfe sogenannte Einwegfunktionen definiert werden können. Weitere Anwendungen finden sich bei der Faktorisierung natürlicher Zahlen.

Der Name der elliptischen Kurven leitet sich historisch davon ab, dass sie elliptische Integrale parametrisieren. Sie sind von Ellipsen zu unterscheiden.

Inhaltsverzeichnis

Elliptische Kurven über den reellen Zahlen

Schaubild der Kurven y2 = x3x und y2 = x3x + 1

Wir definieren elliptische Kurven über dem Körper der reellen Zahlen als die Menge aller Punkte (x,y) \in \mathbb{R}^2, die für reelles a und b die Gleichung

y^2 = x^3 + ax + b \,

lösen. Um die Entstehung von Singularitäten (d.h. von Stellen, an denen sich die Kurve selbst schneidet bzw. scharfe Spitzen oder isolierte Punkte ausbildet) zu verhindern, stellen wir zudem an die Koeffizienten die Bedingung

\Delta := -(4a^3 + 27b^2) \neq 0.

Die Größe Δ ist die Diskriminante des rechts stehenden kubischen Polynoms x3 + ax + b der elliptischen Kurve und hat eine weitere Bedeutung: Für Δ > 0 besteht das Schaubild der elliptischen Kurve aus zwei Komponenten (siehe linkes Bild), für Δ < 0 hingegen nur aus einer einzigen Komponente (rechtes Bild).

Elliptische Kurven über den komplexen Zahlen

Interpretiert man wie üblich die komplexen Zahlen als Elemente der Gaußschen Zahlenebene, so stellen elliptische Kurven über den komplexen Zahlen eine zweidimensionale Fläche dar, die in den vierdimensionalen \mathbb{C}^2 eingebettet ist. Obwohl sich solche Flächen der Anschauung entziehen, lassen sich dennoch Aussagen über ihre Gestalt treffen, wie zum Beispiel über das Geschlecht der Fläche.

Komplexe Tori

Es sei Γ ein (vollständiges) Gitter in der komplexen Zahlenebene \mathbb C. Die Faktorgruppe \mathbb C/\Gamma ist eine eindimensionale abelsche kompakte komplexe Liegruppe, die als reelle Liegruppe isomorph zum Torus S^1\times S^1 ist. Für eine Veranschaulichung kann man Erzeuger v,w von Γ wählen; der Quotient \mathbb C/\Gamma ergibt sich dann aus der Grundmasche

\{\lambda v+\mu w\mid 0\leq\lambda,\mu\leq1\},

indem man jeweils gegenüberliegende Seiten verklebt.

Bezug zu ebenen Kubiken

Ist Γ ein Gitter in der komplexen Zahlenebene, so definieren die zugehörige weierstraßsche p-Funktion und ihre Ableitung eine Einbettung

\mathbb C/\Gamma\to\mathbb P^2(\mathbb C),\quad z\mapsto(1:\wp(z):\wp'(z)),

deren Bild die nichtsinguläre Kubik

y2 = 4x3g2(Γ)xg3(Γ)

ist. Jede nichtsinguläre ebene Kubik ist isomorph zu einer Kubik, die auf diese Weise entsteht.

Klassifikation

Zwei eindimensionale komplexe Tori \mathbb C/\Gamma_1 und \mathbb C/\Gamma_2 für Gitter Γ12 sind genau dann isomorph (als komplexe Liegruppen), wenn die beiden Gitter ähnlich sind, d. h. durch eine Drehstreckung auseinander hervorgehen. Jedes Gitter ist zu einem Gitter der Form \langle1,\tau\rangle_{\mathbb Z} ähnlich, wobei τ ein Element der oberen Halbebene \mathbb H=\{z\in\mathbb C\mid \operatorname{Im}z>0\} ist; sind v,w Erzeuger, so kann τ als v / w oder w / v gewählt werden. Die verschiedenen Wahlen für Erzeuger entsprechen der Operation der Gruppe \mathrm{SL}_2(\mathbb Z) auf der oberen Halbebene, die durch

\begin{pmatrix}a&b\\c&d\end{pmatrix}\tau=\frac{a\tau+b}{c\tau+d}

gegeben ist. Zwei Elemente τ12 der oberen Halbebene definieren genau dann isomorphe elliptische Kurven \mathbb C/\langle1,\tau_1\rangle und \mathbb C/\langle1,\tau_2\rangle, wenn τ1 und τ2 in derselben \mathrm{SL}_2(\mathbb Z)-Bahn liegen; die Menge der Isomorphieklassen elliptischer Kurven entspricht damit dem Quotientenraum

\mathrm{SL}_2(\mathbb Z)/\mathbb H;

dieser Quotient wird von der j-Funktion bijektiv auf \mathbb C abgebildet; dabei ist der Wert der j-Funktion gleich der j-Invarianten der oben angegebenen Kubik.

Elliptische Kurven über den rationalen Zahlen

Die Theorie elliptischer Kurven über dem Körper der rationalen Zahlen ist ein aktives Forschungsgebiet der Zahlentheorie mit einigen berühmten offenen Vermutungen wie der Vermutung von Birch und Swinnerton-Dyer.

Elliptische Kurven über endlichen Körpern

Statt über den rationalen Zahlen kann man auch elliptische Kurven über endlichen Körpern betrachten. In diesem Falle besteht die Ebene, genauer gesagt die projektive Ebene, in der die elliptische Kurve liegt, nur noch aus endlich vielen Punkten. Daher kann auch die elliptische Kurve selbst höchstens noch endlich viele Elemente enthalten, was viele Betrachtungen einfacher machen kann. Von einer Kurve im anschaulichen Sinne kann jedoch keine Rede mehr sein.

Elliptische Kurven über endlichen Körpern werden z. B. in der Kryptographie (Elliptische-Kurven-Kryptosystem) eingesetzt.

Die (bisher noch unbewiesene) Vermutung von Birch und Swinnerton-Dyer versucht, Aussagen über gewisse Eigenschaften elliptischer Kurven über den rationalen Zahlen zu erhalten, indem entsprechende Eigenschaften elliptischer Kurven über endlichen Körpern (sogenannte "reduzierte elliptische Kurven") untersucht werden.

Rechenregeln

Geometrische Interpretation

Aus der Gitterstruktur im Komplexen folgt auch für elliptische Kurven E über den rationalen Zahlen bzw. über endlichen Körpern eine Gruppenstruktur.

Für die rationalen Punkte der elliptischen Kurve (falls sie existieren), wird eine Gruppenstruktur mit „Addition“ angegeben. Geometrisch ist sie so definiert: Der Punkt im Unendlichen ist das neutrale Element \infty. Die Spiegelung eines Punktes P an der x-Achse liefert wieder einen rationalen Punkt der Kurve, das Inverse -P von P. Die Gerade durch die rationalen Punkte P, Q schneidet die Kurve in einem dritten Punkt, Spiegelung dieses Punktes an der x-Achse liefert den rationalen Punkt P + Q.

Im Fall einer Tangente an den Punkt P (also dem Grenzfall Q gegen P auf der Kurve) erhält man mit dieser Konstruktion (Schnittpunkt Tangente mit Kurve, dann Spiegelung) den Punkt P + P. Lassen sich keine entsprechenden Schnittpunkte finden, wird der Punkt im Unendlichen zuhilfe genommen, und man hat z. B. im Fall der Tangente ohne zweiten Schnittpunkt: P + \infty = P.

Man kann zeigen, dass diese „Addition“ sowohl kommutativ als auch assoziativ ist, sodass sie tatsächlich die Gesetze einer abelschen Gruppe erfüllt.

Sei nun P ein Punkt der elliptischen Kurve. Der Punkt P + P wird mit 2P bezeichnet, entsprechend definiert man kP =P + … + P als k-fache Addition des Punktes P. Ist P nicht der 0-Punkt kann auf diese Weise jeder Punkt der Kurve E erreicht werden (d. h. zu jedem Punkt Q auf der Kurve existiert eine natürliche Zahl k mit Q = kP), wenn man die richtigen Erzeugenden P der Gruppe kennt.

Die Aufgabe, aus gegebenen Punkten P, Q diesen Wert k zu ermitteln, wird als Diskretes Logarithmus-Problem der elliptischen Kurven (kurz ECDLP) bezeichnet. Es wird angenommen, dass das ECDLP (bei geeigneter Kurvenwahl) schwer ist, d. h. nicht effizient gelöst werden kann. Damit bieten sich elliptische Kurven an, um auf ihnen asymmetrische Kryptosysteme zu realisieren (etwa einen Diffie-Hellman-Schlüsselaustausch oder ein Elgamal-Kryptosystem).

Addition zweier verschiedener Punkte

Seien P: = (xP,yP) und Q = (xQ,yQ) die Komponenten der Punkte P und Q. Mit R wird das Ergebnis der Addition R \colon{=} P \oplus Q \colon{=} (x_R,y_R) bezeichnet. Dieser Punkt R hat also die Komponenten (xR,yR). Außerdem setze s = (yPyQ) / (xPxQ). Dann ist die Addition P \oplus Q \colon{=} (x_R,y_R) durch

  • xR: = s2xPxQ und
  • yR: = − yP + s(xPxR)

definiert.

Die beiden Punkte P und Q dürfen nicht dieselbe X-Koordinate besitzen, da es sonst nicht möglich ist, die Steigung s zu berechnen, da dann entweder P = Q oder P = − Q gilt. Bei der Addition P \oplus (-P) erhält man s=\tfrac{2y_P}{0}, wodurch das Ergebnis als \infty (neutrales Element) definiert ist. Dadurch ergibt sich auch, dass P und P zueinander invers bezüglich der Punktaddition sind. Ist P = Q, handelt es sich um eine Punktverdoppelung.

Verdoppelung eines Punktes

Für die Punktverdoppelung (Addition eines Punktes zu sich selbst) existieren zwei Fälle.

Fall 1: y_P \neq 0

  • P \oplus P = R = (x_R,y_R)
  • s = (3x_P^2 + a)/(2y_P). Dabei wird a aus der Kurvengleichung (cy2 = x3 + ax + b) herangezogen.
  • xR = s2 − 2xP
  • yR = − yP + s(xPxR)

Der einzige Unterschied zur Addition von zwei verschiedenen Punkten liegt in der Berechnung der Steigung.

Fall 2: yP = 0

  • P \oplus P = \infty

Wegen y_P=0 \Rightarrow P = (-P) ist klar erkennbar, dass P zu sich selbst invers ist.

Rechenregeln für die „Addition“ von Punkten der Kurve

Analytische Beschreibung über die Koordinaten:

Seien

  • P,Q zwei verschiedene Punkte
  • P = (xP,yP)
  • Q = (xQ,yQ)
  • x_P \neq x_Q
  • \oplus die Addition zweier Punkte und
  • \infty das neutrale Element (auch Unendlichkeitspunkt genannt)

Es gelten folgende Regeln:

  • P \oplus Q = Q \oplus P
  • P \oplus (-P) = \infty
  • P \oplus \infty = P
  • P = (xP, − yP)
  • (P \oplus Q) \oplus R = P \oplus (Q \oplus R)

Skalare Multiplikation eines Punktes

Bei der skalaren Multiplikation n\cdot P handelt es sich lediglich um die wiederholte Addition dieses Punktes.

  • n\cdot P = P \oplus \cdots \oplus P

Diese Multiplikation kann unter Zuhilfenahme eines angepassten Square-&-Multiply-Verfahrens effizient gelöst werden.

Bei einer elliptischen Kurve über dem endlichen Körper GF(q) läuft die Punktaddition rechnerisch auf analoge Weise wie bei der Berechnung über \mathbb{R}, jedoch werden die Koordinaten über GF(q) berechnet.

Literatur

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Elliptische-Kurven-Kryptografie — Elliptische Kurve über R Unter Elliptic Curve Cryptosystems (ECC) versteht man asymmetrische Kryptosysteme, die Operationen auf elliptischen Kurven über endlichen Körpern verwenden. Die Sicherheit dieser Verfahren basiert auf der Schwierigkeit… …   Deutsch Wikipedia

  • Elliptische-Kurven-Kryptographie — Elliptische Kurve über R Unter Elliptic Curve Cryptosystems (ECC) versteht man asymmetrische Kryptosysteme, die Operationen auf elliptischen Kurven über endlichen Körpern verwenden. Die Sicherheit dieser Verfahren basiert auf der Schwierigkeit… …   Deutsch Wikipedia

  • Elliptische-Kurven-Kryptosystem — Elliptische Kurve über R Unter Elliptic Curve Cryptosystems (ECC) versteht man asymmetrische Kryptosysteme, die Operationen auf elliptischen Kurven über endlichen Körpern verwenden. Die Sicherheit dieser Verfahren basiert auf der Schwierigkeit… …   Deutsch Wikipedia

  • Elliptische Funktionen — Im mathematischen Teilgebiet der Funktionentheorie sind elliptische Funktionen doppeltperiodische meromorphe Funktionen. „Doppeltperiodisch“ bedeutet, dass es zwei komplexe Zahlen ω1,ω2 gibt, die keine reellen Vielfachen voneinander sind, so dass …   Deutsch Wikipedia

  • Elliptische Funktion — Im mathematischen Teilgebiet der Funktionentheorie sind elliptische Funktionen doppeltperiodische meromorphe Funktionen. „Doppeltperiodisch“ bedeutet, dass es zwei komplexe Zahlen ω1,ω2 gibt, die linear unabhängig im reellen Vektorraum sind, so… …   Deutsch Wikipedia

  • Elliptische Räder [1] — Elliptische Räder geben, als Zahnräder mit elliptischem Teilriß, periodisch wechselndes Uebersetzungsverhältnis. Man benutzt sie in der Regel in Verbindung mit einem Kurbelgetriebe, entweder nach Fig. 1 so, daß zwei Ellipsenräder, je um einen… …   Lexikon der gesamten Technik

  • Kurve — steht für einen Bogen im Sinne des Straßen und Schienenbaus, siehe Trassierungselement, einen Teil eines Stadions, siehe Fankurve, und verschiedene mathematische Objekte, nämlich für eindimensionale Objekte, die im Allgemeinen eine Krümmung… …   Deutsch Wikipedia

  • Weierstraßsche elliptische Funktion — Im mathematischen Teilgebiet der Funktionentheorie sind elliptische Funktionen doppeltperiodische meromorphe Funktionen. „Doppeltperiodisch“ bedeutet, dass es zwei komplexe Zahlen ω1,ω2 gibt, die keine reellen Vielfachen voneinander sind, so dass …   Deutsch Wikipedia

  • Jacobische elliptische Funktion — In der Mathematik ist eine Jacobische elliptische Funktion eine von zwölf speziellen elliptischen Funktionen. Die Jacobischen elliptischen Funktionen haben einige Analogien zu den trigonometrischen Funktionen und finden zahlreiche Anwendungen in… …   Deutsch Wikipedia

  • Algebraische Kurve — Eine algebraische Kurve ist eine eindimensionale algebraische Varietät, kann also durch eine Polynomgleichung beschrieben werden. Ein wichtiger Spezialfall sind die ebenen algebraischen Kurven, also algebraische Kurven, die in der affinen oder… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”