Elliptische Kurve

spezielle algebraische Kurven mit geometrisch definierter Addition

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).

Elliptische Kurve über dem Körper der reellen Zahlen

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.

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

Bearbeiten

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).[1]

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

Bearbeiten

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

Bearbeiten

  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

Bearbeiten

Definition

Bearbeiten

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

Bearbeiten

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

Bearbeiten
 
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

Bearbeiten

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

Bearbeiten

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

Bearbeiten
 
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

Bearbeiten

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

Bearbeiten

Analytische Beschreibung über die Koordinaten:

Seien

  •   zwei verschiedene Punkte,
  •  
  •  
  •  
  •   die Addition zweier Punkte und
  •   das neutrale Element (auch Unendlichkeitspunkt genannt).

Es gelten folgende Regeln:

  •  
  •  
  •  
  •  
  •  

Skalare Multiplikation eines Punktes

Bearbeiten

Bei der skalaren Multiplikation   handelt es sich lediglich um die wiederholte Addition dieses Punktes.

  •  

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

Bei einer elliptischen Kurve über dem endlichen Körper   läuft die Punktaddition rechnerisch auf analoge Weise wie bei der Berechnung über  , jedoch werden die Koordinaten über   berechnet.

Elliptische Kurven über den komplexen Zahlen

Bearbeiten

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   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, in diesem Fall (Torus) vom Geschlecht 1.

Komplexe Tori

Bearbeiten

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

 ,

indem man jeweils gegenüberliegende Seiten verklebt.

Bezug zu ebenen Kubiken

Bearbeiten
 
Eine elliptische Kurve ist in der komplexen Ebene durch eine elliptische Funktion definiert über deren Werte in einem Gitter  , das durch die komplexen Perioden   und   aufgespannt ist. Eingezeichnet sind auch die Torsionspunkte vierter Ordnung, die einem Gitter   entsprechen

Die Funktionen, die elliptische Kurven parametrisieren, bilden eine große Familie und haben besondere Eigenschaften. Da sie auf einer Ebene und nicht nur auf einer Zahlengeraden definiert sind, kann man ihnen sogar Periodizität in zwei Richtungen gleichzeitig abverlangen. Genannt werden diese Funktionen auch p-Funktionen. Man verwendet für sie die Bezeichnung  , wobei für den komplexen Parameter die Bezeichnung   üblicher als   ist.[2]

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

 ,

deren Bild die nichtsinguläre Kubik

 

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

Auch analog zu Sinus und Kosinus findet man, dass die zu   gehörige  -Koordinate die Ableitung von   ist, also  . Diese ist wieder eine doppeltperiodische Funktion und es gilt   (hier ist zwar noch eine 4 vor dem  , aber diese kann durch Umformungen eliminiert werden). Diese Gleichung ähnelt   und kann über den Ansatz   begründet werden. Es lässt sich zeigen, dass die linke Funktion auf der Periodenmasche beschränkt ist und eine Nullstelle hat, und aus einem Satz der Funktionentheorie folgt dann mittels der Doppeltperiodizität bereits, dass sie konstant den Wert 0 annimmt.

Bei diesem Verfahren muss darauf geachtet werden, dass die Wahl der p-Funktion (und damit die Wahl der passenden Periodenmasche) entscheidend von den Zahlen   und   in der Gleichung   abhängt.[3]

Die elliptische Funktion ist über ihre Weierstraßform in einem Gitter   der komplexen Ebene definiert, da die Funktion doppeltperiodisch ist (Perioden  ,  , beides komplexe Zahlen,   für ein reelles  ). Die Ränder des Gitters werden identifiziert, was geometrisch einen Torus ergibt. Durch die obige Abbildung wird das Gitter in die komplexe projektive Ebene abgebildet und die Addition von Punkten im Quotientenraum (Torus)   überträgt sich als Gruppenhomomorphismus auf die elliptische Kurve in der projektiven Ebene, was das oben erläuterte „Additionsgesetz“ von Punkten auf der Kurve ergibt.

Punkte von endlicher Ordnung im Gitter heißen Torsionspunkte. Ein Torsionspunkt  -ter Ordnung entspricht den Punkten

 

mit  . In der Abbildung ist der Fall   dargestellt. Bezüglich des oben definierten Additionsgesetzes für Punkte auf elliptischen Kurven gilt für einen  -Torsionspunkt   die Gleichung  .

Klassifikation

Bearbeiten

Zwei eindimensionale komplexe Tori   und   für Gitter   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   ähnlich, wobei   ein Element der oberen Halbebene   ist; sind   Erzeuger, so kann   als   oder   gewählt werden. Die verschiedenen Wahlen für Erzeuger entsprechen der Operation der Gruppe   auf der oberen Halbebene, die durch

 

gegeben ist (Modulgruppe). Zwei Elemente   der oberen Halbebene definieren genau dann isomorphe elliptische Kurven   und  , wenn   und   in derselben  -Bahn liegen; die Menge der Isomorphieklassen elliptischer Kurven entspricht damit dem Bahnenraum

 

dieser Raum wird von der   -Funktion, einer Modulfunktion, bijektiv auf   abgebildet; dabei ist der Wert der  -Funktion gleich der  -Invarianten der oben angegebenen Kubik.

Elliptische Kurven über den rationalen Zahlen

Bearbeiten

Die Addition von Punkten elliptischer Kurven ermöglicht es, aus einfachen (geratenen) Lösungen einer kubischen Gleichung weitere Lösungen zu berechnen, die in der Regel weitaus größere Zähler und Nenner   haben als die Ausgangslösungen (und deshalb kaum durch systematisches Probieren zu finden wären).

Zum Beispiel für die über   definierte elliptische Kurve

 

findet man durch Raten die Lösung   und daraus durch Addition auf der elliptischen Kurve die Lösung   sowie durch weitere Addition auf der elliptischen Kurve dann noch erheblich „größere“ Lösungen. Das ergibt sich aus

 

für Punkte mit ganzzahligen Koordinaten auf elliptischen Kurven über   unter Verwendung der Koordinatenform des Additionsgesetzes (siehe oben). Dabei ist   die für ganzzahlige Punkte durch   definierte Höhe.

Die Gruppe der rationalen Punkte   auf   einschließlich   ist die Mordell-Weil-Gruppe  . Nach dem Satz von Mordell-Weil ist   endlich erzeugt und es gilt  , wobei   die Torsionsuntergruppen sind und   den (algebraischen) Rang[4] der elliptischen Kurve bezeichnet. Somit kann jeder Punkt   mit festen   sowie   aus einem endlichen Lösungsvorrat geschrieben werden.[5] Allgemeiner für einen Körper   bezeichnet die Gruppe   alle K-rationalen Punkte, deren Ordnung ein Teiler von   ist.

Nach dem Satz von Lutz und Nagell (Élisabeth Lutz, Trygve Nagell, Mitte der 1930er Jahre) gilt für die Torsionspunkte, also die Punkte   endlicher Ordnung (also die Elemente der Torsionsuntergruppen), dass   und entweder   (dann ist   von der Ordnung 2) oder  , das heißt,   teilt   (wobei   die Diskriminante ist). Das ermöglicht es, die Torsionsuntergruppen   zu berechnen.

Die möglichen Torsionsuntergruppen für elliptische Kurven über den rationalen Zahlen wurden von Barry Mazur klassifiziert in einem schwierigen Beweis (Satz von Mazur (elliptische Kurven)). Danach kann bei einem Punkt der Ordnung   die Zahl   einen der Werte 1 bis 10 oder 12 annehmen.

Mit dem Satz von Lutz und Nagell und dem von Mazur hat man einen Algorithmus zur Bestimmung der Elemente   der Torsionsgruppe   einer elliptischen Kurve   über den rationalen Zahlen  :[6]

  • Man finde   mit der Diskriminante   der Kurve.
  • Man bestimme die zugehörigen   aus der Gleichung der Kurve und hat so die Koordinaten von  .
  • Man berechne   mit   (nach dem Satz von Mazur), ist   (wobei hier die Notation   für das neutrale Element verwendet wird), so hat man einen Torsionspunkt. Hat dagegen   keine ganzzahligen Koordinaten, gehört er nicht zu den Torsionspunkten.

Elliptische Kurven nehmen nach der Vermutung von Mordell (Satz von Faltings, sie entsprechen dort dem Fall des Geschlechts  ) eine Sonderstellung ein, sie können unendlich viele (Rang ungleich null) oder endlich viele rationale Lösungen (Torsionsuntergruppen) haben. Kurven mit   haben dagegen nur endlich viele Lösungen. Im Fall   gibt es keine oder unendlich viele Lösungen (zum Beispiel beim Kreis unendlich viele pythagoreische Tripel).

Die Theorie elliptischer Kurven über dem Körper der rationalen Zahlen ist ein aktives Forschungsgebiet der Zahlentheorie (arithmetische algebraische Geometrie) mit einigen berühmten offenen Vermutungen wie der Vermutung von Birch und Swinnerton-Dyer, die eine Aussage über das analytische Verhalten die Hasse-Weil-L-Funktion   einer elliptischen Kurve macht, in deren Definition die Anzahl der Punkte der Kurve über endlichen Körpern einfließt. Nach der Vermutung in ihrer einfachsten Form ist der Rang der elliptischen Kurve gleich der Ordnung der Nullstelle von   bei  .

Elliptische Kurven über endlichen Körpern

Bearbeiten
 
Affine Punkte der elliptischen Kurve   über  

Statt über den rationalen Zahlen kann man elliptische Kurven auch ü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 nur endlich viele Elemente enthalten, was viele Betrachtungen vereinfachen kann. Für die Anzahl   der Punkte einer elliptischen Kurve   über einem Körper mit   Elementen zeigte Helmut Hasse (1936) die Abschätzung (riemannsche Vermutung)[7]

 

und bewies damit eine Vermutung aus der Dissertation von Emil Artin (1924).[8]

Allgemeiner folgt aus den Weil-Vermutungen (einer Reihe von Vermutungen zur Hasse-Weil-Zetafunktion, bewiesen in den 1960er und 1970er Jahren) für die Anzahl   der Punkte von   über einer Körpererweiterung mit   Elementen die Gleichung[9]

 ,

wobei   und   die beiden Nullstellen des charakteristischen Polynoms des Frobeniushomomorphismus   auf der elliptischen Kurve über   sind. René Schoof (1985) entwickelte den ersten effizienten Algorithmus zur Berechnung von  . Es folgten Verbesserungen von A. O. L. Atkin (1992) und Noam Elkies (1990).

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.

Hasse-Weil-Zetafunktion und L-Funktion für elliptische Kurven

Bearbeiten

Die elliptische Kurve   über   sei durch die Gleichung

 

mit ganzzahligen Koeffizienten   gegeben. Die Reduktion der Koeffizienten modulo einer Primzahl   definiert eine elliptische Kurve über dem endlichen Körper   (mit Ausnahme einer endlichen Menge von Primzahlen  , für welche die reduzierte Kurve Singularitäten aufweist und deshalb nicht elliptisch ist; in diesem Fall sagt man,   habe schlechte Reduktion bei  ).

Die Zetafunktion einer elliptischen Kurve über einem endlichen Körper ist die formale Potenzreihe

 

Sie ist eine rationale Funktion der Form

 

(Diese Gleichung definiert den Koeffizienten  , falls   gute Reduktion bei   hat, die Definition im Fall schlechter Reduktion ist eine andere.)

Die  -Funktion von   über   speichert diese Information für alle Primzahlen  . Sie ist definiert durch

 

mit  , falls   gute Reduktion bei   hat, und   sonst.

Das Produkt konvergiert für  . Hasse vermutete (Riemannsche Vermutung für Elliptische Kurven), dass die  -Funktion eine analytische Fortsetzung auf die gesamte komplexe Ebene besitzt und eine Funktionalgleichung mit einem Zusammenhang zwischen   und   erfüllt. Hasses Vermutung wurde 1999 als Konsequenz des Beweises des Modularitätssatzes bewiesen. Dieser besagt, dass jede elliptische Kurve über   eine modulare Kurve ist (also durch Modulfunktionen parametrisiert werden kann), und für die  -Funktionen modularer Kurven ist die analytische Fortsetzbarkeit bekannt.

Anwendung in der Kryptographie

Bearbeiten

Der US-Auslandsgeheimdienst NSA empfahl im Januar 2009, Verschlüsselung im Internet bis 2020 von RSA auf ECC (Elliptic Curve Cryptography) umzustellen.[10]

ECC ist ein Public-Key-Kryptosystem (oder asymmetrisches Kryptosystem), bei dem im Gegensatz zu einem symmetrischen Kryptosystem die kommunizierenden Parteien keinen gemeinsamen geheimen Schlüssel kennen müssen. Asymmetrische Kryptosysteme allgemein arbeiten mit Falltürfunktionen, also Funktionen, die leicht zu berechnen, aber ohne ein Geheimnis (die „Falltür“) praktisch unmöglich zu invertieren sind.

Die Verschlüsselung mittels elliptischer Kurven funktioniert im Prinzip so, dass man die Elemente der zu verschlüsselnden Nachricht (d. h. die einzelnen Bits) auf irgendeine Weise den Punkten   einer (festen) elliptischen Kurve zuordnet und dann die Verschlüsselungsfunktion   mit einer (festen) natürlichen Zahl   anwendet. Damit dieses Verfahren sicher ist, muss die Entschlüsselungsfunktion   schwer zu berechnen sein.

Da das Problem des diskreten Logarithmus in elliptischen Kurven (ECDLP) deutlich schwerer ist als die Berechnung des diskreten Logarithmus in endlichen Körpern oder die Faktorisierung ganzer Zahlen, kommen Kryptosysteme, die auf elliptischen Kurven beruhen – bei vergleichbarer Sicherheit – mit erheblich kürzeren Schlüsseln aus als die herkömmlichen asymmetrischen Kryptoverfahren, wie z. B. das RSA-Kryptosystem. Die derzeit schnellsten Algorithmen sind der Babystep-Giantstep-Algorithmus und die Pollard-Rho-Methode, deren Laufzeit bei   liegt, wobei   die Bitlänge der Größe des zugrundeliegenden Körpers ist.

Literatur

Bearbeiten
Bearbeiten
Commons: Elliptic curves – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

Bearbeiten
  1. Elliptische Kurve. In: Guido Walz (Hrsg.): Lexikon der Mathematik. 1. Auflage. Spektrum Akademischer Verlag, Mannheim/Heidelberg 2000, ISBN 3-8274-0439-8.
  2. Neal Koblitz: Introduction to Elliptic Curves and Modular Forms. Springer-Verlag New York, S. 16.
  3. Neal Koblitz: Introduction to Elliptic Curves and Modular Forms. Springer-Verlag New York, S. 24.
  4. History of elliptic curves rank records
  5. Don Zagier: "Lösungen von Gleichungen in ganzen Zahlen", S. 311–326
  6. Zachary DeStefano: On the torsion subgroup of an elliptic curve. Vorlesung, New York University 2010, PDF.
  7. Helmut Hasse: Zur Theorie der abstrakten elliptischen Funktionenkörper. I, II & III. In: Journal für die reine und angewandte Mathematik. Band 1936, Nr. 175, 1936, doi:10.1515/crll.1936.175.193.
  8. Emil Artin: Quadratische Körper im Gebiete der höheren Kongruenzen. II. Analytischer Teil. In: Mathematische Zeitschrift. Band 19, Nr. 1, 1924, S. 207–246, doi:10.1007/BF01181075.
  9. Kapitel V, Theorem 2.3.1 in Joseph H. Silverman: The Arithmetic of Elliptic Curves. 2. Auflage. Springer, 2009, ISBN 978-0-387-09493-9.
  10. The Case for Elliptic Curve Cryptography. In: nsa.gov. 15. Januar 2009, archiviert vom Original am 19. Januar 2009; abgerufen am 28. April 2016 (englisch).