mini|hochkant=1.2|Elliptische Kurve über dem Körper der reellen Zahlen In der Mathematik sind elliptische Kurven spezielle algebraische Kurven, auf denen geometrisch eine Addition definiert ist. Diese Addition wird in der Kryptographie zur Konstruktion sicherer Verschlüsselungsmethoden verwendet. Elliptische Kurven spielen aber auch in der reinen Mathematik eine wichtige Rolle. Historisch sind sie durch die Parametrisierung elliptischer Integrale entstanden als deren Umkehrfunktionen (elliptische Funktionen).

Eine elliptische Kurve ist eine glatte algebraische Kurve der Ordnung 3 in der projektiven Ebene. Dargestellt werden elliptische Kurven meist als Kurven in der affinen Ebene, sie besitzen aber noch einen zusätzlichen Punkt im Unendlichen.

Elliptische Kurven über dem Körper der reellen Zahlen können als die Menge aller (affinen) Punkte angesehen werden, die die Gleichung

erfüllen, zusammen mit einem sogenannten Punkt im Unendlichen (notiert als oder ). Die (reellen) Koeffizienten und müssen dabei die Bedingung erfüllen, dass für die Diskriminante des kubischen Polynoms in auf der rechten Seite gilt, um Singularitäten auszuschließen (die Wurzeln des Polynoms sind dann paarweise verschieden, die Kurve hat keine Doppelpunkte oder andere Singularitäten).

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 dem Körper der komplexen Zahlen stammen. Ausführlich untersucht wurden auch elliptische Kurven über dem Körper der rationalen Zahlen, über endlichen Körpern und über p-adischen Körpern. Die Theorie der elliptischen Kurven verbindet daher sehr unterschiedliche Teilgebiete der Mathematik. Die Untersuchung elliptischer Kurven über den rationalen Zahlen oder endlichen Körpern ist Gegenstand der Zahlentheorie und ein Spezialfall der auch in höheren Dimensionen betrachteten abelschen Varietäten. Ihre Untersuchung über den komplexen Zahlen ist ein klassisches Gebiet der Funktionentheorie.

Jede elliptische Kurve über den komplexen Zahlen kann mit Hilfe eines Gitters in der komplexen Zahlenebene als komplexer Torus dargestellt werden, was sich schon aus der doppelten Periodizität elliptischer Funktionen ergibt (siehe Weierstraßsche elliptische Funktion). Ihre riemannsche Fläche ist topologisch ein Torus und über die zugehörige Aufteilung der komplexen Ebene durch ein Gitter eine abelsche Gruppe. Diese Gruppenstruktur überträgt sich auch auf elliptischen Kurven über den rationalen Zahlen und auf eine besondere Art von Addition für Punkte auf elliptischen Kurven (siehe unten). Der Mathematiker Andrew Wiles bewies im Jahr 1994 (veröffentlicht 1995) den Modularitätssatz für spezielle elliptische Kurven, der besagt, dass alle entsprechenden Kurven über den rationalen Zahlen durch Modulformen parametrisiert werden. Mit Hilfe dieses Satzes konnte der Große Fermatsche Satz bewiesen werden, eine bekannte zahlentheoretische Aussage, die sich einfach formulieren, aber nur schwer beweisen lässt.

Praktische Anwendung finden elliptische Kurven in modernen Verschlüsselungsverfahren (Elliptische-Kurven-Kryptosystem), die die oben erwähnte besondere Addition von Punkten auf elliptischen Kurven für die Definition von Einwegfunktionen verwenden. Weitere Anwendungen finden sich bei der Faktorisierung natürlicher Zahlen. 392px|mini|Lösungen der Gleichung für verschiedene Werte von . Im Fall ist die Kurve singulär und damit keine elliptische Kurve

Werden statt kubischer Polynome solche höheren als vierten Grades betrachtet, erhält man hyperelliptische Kurven (die höheres topologisches Geschlecht haben).

Geschichte

Die Theorie der elliptischen Kurven entwickelte sich zunächst im Kontext der Funktionentheorie. Bei verschiedenen geometrischen oder physikalischen Problemen – so zum Beispiel bei der Bestimmung der Bogenlänge von Ellipsen – treten elliptische Integrale auf. Zu diesen Integralfunktionen konnten Umkehrfunktionen bestimmt werden. Diese meromorphen Funktionen wurden aufgrund dieses Kontextes als elliptische Funktionen bezeichnet (für deren Geschichte siehe dort). Wie weiter unten dargestellt wird, kann man mittels elliptischer Funktionen auf eindeutige Weise jeder elliptischen Kurve über dem Körper der komplexen Zahlen einen Torus zuordnen. Auf diese Weise können dann die elliptischen Kurven klassifiziert werden und aufgrund dieses Zusammenhangs haben sie ihren Namen erhalten.

Seit dem Ende des 19. Jahrhunderts stehen arithmetische und zahlentheoretische Fragestellungen im Zentrum der Theorie. Es konnte gezeigt werden, dass elliptische Kurven sinnvoll auf allgemeinen Körpern definiert werden können, und es wurde – wie zuvor schon beschrieben – gezeigt, dass eine elliptische Kurve als kommutative Gruppe interpretiert werden kann (was auf Henri Poincaré zurückgeht).

In den 1990er Jahren konnte Andrew Wiles nach Vorarbeiten von Gerhard Frey und anderen mittels der Theorie der elliptischen Kurven die fermatsche Vermutung aus dem 17. Jahrhundert beweisen.

Affine und projektive Ebene

Der zweidimensionale Raum der -rationalen projektiven Punkte ist definiert als

mit der Äquivalenzrelation . Punkte aus werden üblicherweise als notiert, um sie von Punkten im dreidimensionalen affinen Raum zu unterscheiden.

Die projektive Ebene kann dargestellt werden als Vereinigung der Menge

mit der durch erzeugten Hyperebene von :

Um projektive Kubiken in der affinen Ebene darzustellen, identifiziert man dann für den projektiven Punkt mit dem affinen Punkt .

Im Fall einer elliptischen Kurve hat die (projektive) Polynomgleichung genau eine Lösung mit , nämlich den Punkt im Unendlichen .

Definition

heißt elliptische Kurve über dem Körper , falls eine der folgenden (paarweise äquivalenten) Bedingungen erfüllt ist:

ist eine glatte projektive Kurve über vom Geschlecht 1 mit einem Punkt , dessen Koordinaten in liegen. ist eine glatte projektive Kubik über mit einem Punkt , dessen Koordinaten in liegen. ist eine glatte, (bis auf Isomorphie) durch eine Weierstraß-Gleichung

gegebene projektive Kurve mit Koeffizienten . Schreibt man

so ist gerade die Nullstellenmenge des homogenen Polynoms . (Beachte: Der Punkt erfüllt auf jeden Fall die Polynomgleichung, liegt also auf .)

Fasst man als affine Kurve auf, so erhält man eine affine Weierstraß-Gleichung

(in langer Weierstraß-Form / Weierstraßnormalform) bzw. ein affines Polynom . In diesem Fall ist gerade die Menge der (affinen) Punkte, die die Gleichung erfüllen, zusammen mit dem sogenannten „unendlich fernen Punkt“ , auch als geschrieben.

Isomorphe elliptische Kurven Definition

Jede elliptische Kurve wird durch ein projektives Polynom bzw. durch ein affines Polynom beschrieben. Man nennt zwei elliptische Kurven und isomorph, wenn die Weierstraß-Gleichung von aus der von durch einen Koordinatenwechsel der Form

mit entsteht. Die wichtigsten Eigenschaften elliptischer Kurven verändern sich nicht, wenn ein solcher Koordinatenwechsel durchgeführt wird.

Kurze Weierstraß-Gleichung

Ist eine elliptische Kurve über einem Körper mit Charakteristik durch die Weierstraß-Gleichung

gegeben, so existiert ein Koordinatenwechsel, der diese Weierstraß-Gleichung in die Gleichung

transformiert. Diese nennt man eine kurze Weierstraß-Gleichung. Die durch diese kurze Weierstraß-Gleichung definierte elliptische Kurve ist zur ursprünglichen Kurve isomorph. Häufig geht man daher ohne Einschränkung davon aus, dass eine elliptische Kurve von vorneherein durch eine kurze Weierstraß-Gleichung gegeben ist.

Ein weiteres Resultat der Theorie der Weierstraß-Gleichungen ist, dass eine Gleichung der (kurzen Weierstraß-)Form

genau dann eine glatte Kurve beschreibt, wenn die Diskriminante des Polynoms ,

nicht verschwindet. Die Diskriminante ist proportional dem Produkt mit den Wurzeln des kubischen Polynoms und verschwindet nicht, wenn die Wurzeln paarweise verschieden sind.

Beispiele gerahmt|rechts|Schaubild beispielhafter Kurven

und sind elliptische Kurven über , da und sind. ist eine elliptische Kurve sowohl über als auch über , da die Diskriminante ist. Über einem Körper mit Charakteristik dagegen ist und singulär, also keine elliptische Kurve. ist über jedem Körper mit Charakteristik ungleich eine elliptische Kurve, da ist.

Über den reellen Zahlen gibt die Diskriminante eine Information über die Form der Kurve in der affinen Ebene. Für besteht der Graph der elliptischen Kurve aus zwei Komponenten (linke Abbildung), für hingegen nur aus einer einzigen Komponente (rechte Abbildung).

Gruppengesetz

Elliptische Kurven haben die Besonderheit, dass sie bezüglich der in diesem Abschnitt beschriebenen punktweisen Addition kommutative Gruppen sind. Im ersten Unterabschnitt wird diese Addition geometrisch veranschaulicht, bevor sie dann in den folgenden Abschnitten weiter formalisiert wird.

Geometrische Interpretation

Geometrisch kann die Addition zweier Punkte einer elliptischen Kurve wie folgt beschrieben werden: Der Punkt im Unendlichen ist das neutrale Element . Die Spiegelung eines rationalen Punktes an der -Achse liefert wieder einen rationalen Punkt der Kurve, das Inverse von . Die Gerade durch die rationalen Punkte schneidet die Kurve in einem dritten Punkt, Spiegelung dieses Punktes an der -Achse liefert den rationalen Punkt .

Im Fall einer Tangente an den Punkt (also des Grenzfalles auf der Kurve) erhält man mit dieser Konstruktion (Schnittpunkt der Tangente mit der Kurve, dann Spiegelung) den Punkt . Lassen sich keine entsprechenden Schnittpunkte finden, wird der Punkt im Unendlichen zu Hilfe genommen, und man hat z. B. im Fall der Tangente ohne zweiten Schnittpunkt: . Häufig wird der neutrale Punkt auch mit bezeichnet. Der Punkt wird mit bezeichnet, entsprechend definiert man als -fache Addition des Punktes .

Man kann zeigen, dass diese „Addition“ sowohl kommutativ als auch assoziativ ist, sodass sie tatsächlich die Gesetze einer abelschen Gruppe erfüllt. Zum Beweis des Assoziativgesetzes kann dabei der Satz von Cayley-Bacharach eingesetzt werden.

Sei nun ein rationaler Punkt der elliptischen Kurve. Ist nicht der Punkt , kann auf diese Weise jeder rationale Punkt der Kurve erreicht werden (d. h., zu jedem Punkt auf der Kurve existiert eine natürliche Zahl mit ), wenn man die richtigen Erzeugenden der Gruppe kennt.

Die Aufgabe, aus gegebenen Punkten diesen Wert zu ermitteln, wird als Diskreter-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

mini|Addition auf der elliptischen Kurve Seien und die Komponenten der Punkte und . Mit wird das Ergebnis der Addition bezeichnet. Dieser Punkt hat also die Komponenten . Außerdem setze . Dann ist die Addition durch und

definiert.

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

Verdoppelung eines Punktes

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

Fall 1:

. Dabei wird aus der Kurvengleichung () herangezogen.

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

Fall 2:

Wegen ist klar erkennbar, dass zu sich selbst invers ist.

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