Elliptische Kurve – einfach erklärt

Grundidee und Definition

Eine elliptische Kurve ist eine spezielle glatte algebraische Kurve der Ordnung 3 in der projektiven Ebene. „Glatt“ bedeutet, dass die Kurve keine Doppelpunkte oder anderen Singularitäten besitzt. Elliptische Kurven sind besonders wichtig, weil auf ihren Punkten geometrisch eine kommutative Gruppenaddition definiert werden kann. Diese Struktur wird unter anderem in der Zahlentheorie und in der Kryptographie genutzt.

Über den reellen Zahlen besteht eine elliptische Kurve in kurzer Weierstraß-Form aus allen Punkten (x,y) ∈ ℝ², die y² = x³ + ax + b erfüllen, zusammen mit dem Punkt im Unendlichen ∞ beziehungsweise 𝒪. Die Koeffizienten a und b müssen so gewählt sein, dass 4a³ + 27b² ≠ 0 gilt. Äquivalent dazu ist die Diskriminante Δ_E = −4a³ − 27b² des kubischen Polynoms x³ + ax + b ungleich null. Dann sind dessen Wurzeln paarweise verschieden.

Allgemeiner wird eine elliptische Kurve über einem Körper K als glatte projektive Kurve vom Geschlecht 1 mit einem K-rationalen Punkt 𝒪 definiert. Gleichwertig ist sie eine glatte projektive Kubik oder eine glatte Kurve, die bis auf Isomorphie durch eine Weierstraß-Gleichung gegeben ist: Y²Z + a₁XYZ + a₃YZ² = X³ + a₂X²Z + a₄XZ² + a₆Z³, mit aᵢ ∈ K. In der affinen Ebene lautet diese Gleichung y² + a₁xy + a₃y = x³ + a₂x² + a₄x + a₆; zur Kurve gehört zusätzlich 𝒪.

Die projektive Ebene identifiziert dabei Punkte (X:Y:Z), die sich nur durch Multiplikation aller Koordinaten mit demselben λ ∈ K* unterscheiden. Für Z ≠ 0 erhält man affine Koordinaten x = X/Z und y = Y/Z. Eine elliptische Kurve besitzt genau einen Punkt mit Z = 0, nämlich 𝒪 = (0:1:0).

Bei Charakteristik char(K) ≠ 2,3 kann jede Weierstraß-Gleichung durch einen Koordinatenwechsel in die kurze Form y² = x³ + ax + b überführt werden. Zwei Kurven gelten als isomorph, wenn sie durch x ↦ u²x + r und y ↦ u³y + su²x + t mit u ≠ 0 auseinander hervorgehen. Beispiele sind y² = x³ − x + 1 mit Δ_E = −23 und y² = x³ + 2x − √3 mit Δ_E = −113. Die Kurve y² = x³ + 1 ist über jedem Körper der Charakteristik ungleich 3 elliptisch. Höhere Kurven y² = f(x) mit Grad größer als 4 führen zu hyperelliptischen Kurven.

Gruppengesetz und Rechenregeln

Die Punkte einer elliptischen Kurve bilden zusammen mit der Punktaddition eine abelsche, also kommutative Gruppe. Das neutrale Element ist der Punkt im Unendlichen ∞ beziehungsweise 𝒪. Das Inverse eines Punktes P = (x_P,y_P) ist −P = (x_P,−y_P), also die Spiegelung an der x-Achse.

Für zwei verschiedene Punkte P = (x_P,y_P) und Q = (x_Q,y_Q) mit x_P ≠ x_Q wird zunächst die Steigung der Verbindungsgeraden berechnet: s = (y_P − y_Q)/(x_P − x_Q). Schneidet die Gerade die Kurve in einem dritten Punkt, wird dieser an der x-Achse gespiegelt. Das Ergebnis R = P + Q = (x_R,y_R) besitzt die Koordinaten x_R = s² − x_P − x_Q und y_R = −y_P + s(x_P − x_R).

Für Q = −P ist die Verbindungsgerade beziehungsweise die entsprechende Konstruktion senkrecht, und man definiert P + (−P) = ∞. Außerdem gelten P + ∞ = P, P + Q = Q + P und (P + Q) + R = P + (Q + R). Die Assoziativität kann mit dem Satz von Cayley-Bacharach bewiesen werden.

Bei der Verdoppelung P + P wird die Tangente im Punkt P verwendet. Für P = (x_P,y_P) mit y_P ≠ 0 lautet die Tangentensteigung bei y² = x³ + ax + b: s = (3x_P² + a)/(2y_P). Danach gilt x_R = s² − 2x_P und y_R = −y_P + s(x_P − x_R). Ist y_P = 0, dann ist P = −P und deshalb P + P = ∞.

Die skalare Multiplikation n·P bedeutet wiederholte Addition: n·P = P + ⋯ + P. Sie kann mit einem angepassten Square-and-Multiply-Verfahren effizient berechnet werden. Die Frage, aus P und Q die Zahl k zu bestimmen, für die Q = kP gilt, heißt Diskretes-Logarithmus-Problem für elliptische Kurven (ECDLP).

Komplexe Tori und Klassifikation

Über den komplexen Zahlen stellt eine elliptische Kurve eine zweidimensionale Fläche in ℂ² dar. Ihre Riemannsche Fläche hat Geschlecht 1 und ist topologisch ein Torus. Dieser Zusammenhang erklärt die Verbindung zu elliptischen Funktionen und ermöglicht eine Klassifikation.

Ist Γ ein vollständiges Gitter in der komplexen Zahlenebene ℂ, dann ist der Quotient ℂ/Γ eine eindimensionale abelsche kompakte komplexe Liegruppe. Als reelle Liegruppe ist er isomorph zu S¹ × S¹. Wählt man Erzeuger v,w des Gitters, entsteht der Quotient aus der Grundmasche {λv + μw | 0 ≤ λ, μ ≤ 1}, indem gegenüberliegende Seiten verklebt werden.

Die Weierstraßsche ℘-Funktion und ihre Ableitung bilden den Quotienten in die projektive Ebene ab: z ↦ (1:℘(z):℘′(z)). Das Bild ist die nichtsinguläre Kubik y² = 4x³ − g₂(Γ)x − g₃(Γ). Jede nichtsinguläre ebene Kubik ist isomorph zu einer auf diese Weise entstehenden Kubik. Die Funktionen sind doppeltperiodisch; ihre Werte wiederholen sich in zwei Richtungen nach den Perioden ω₁ und ω₂. Es gilt ℘′(z)² = 4℘(z)³ + a℘(z) + b. Die Wahl der passenden Funktion und des Gitters hängt von a und b ab.

Punkte endlicher Ordnung im Quotienten heißen Torsionspunkte. Ein Torsionspunkt n-ter Ordnung entspricht den Punkten kω₁/n + lω₂/n mit k,l = 0,…,n−1 und erfüllt bezüglich des Gruppengesetzes n·P = ∞.

Zwei komplexe Tori ℂ/Γ₁ und ℂ/Γ₂ sind genau dann isomorph, wenn ihre Gitter ähnlich sind, also durch eine Drehstreckung auseinander hervorgehen. Jedes Gitter ist ähnlich zu ⟨1,τ⟩_ℤ mit τ in der oberen Halbebene ℍ = {z ∈ ℂ | Im z > 0}. Verschiedene Erzeuger werden durch die Modulgruppe SL₂(ℤ) mit τ ↦ (aτ+b)/(cτ+d) beschrieben. Zwei Parameter definieren genau dann isomorphe elliptische Kurven, wenn sie in derselben SL₂(ℤ)-Bahn liegen. Die j-Funktion bildet den Bahnenraum SL₂(ℤ)\ℍ bijektiv auf ℂ ab.

Elliptische Kurven über den rationalen Zahlen

Die Punktaddition ermöglicht es, aus einer einfachen rationalen Lösung einer kubischen Gleichung weitere, oft sehr große rationale Lösungen zu berechnen. Für y² = x³ − 63 ist P = (4,1) eine Lösung. Durch Verdoppelung erhält man 2P = (568,−13537); weitere Additionen liefern noch größere Lösungen. Für ganzzahlige Punkte beschreibt die Höhe h(x,y) = log|x| dieses Wachstum, unter anderem durch h(2P) = 4h(P) + O(1).

Die rationalen Punkte einschließlich ∞ bilden die Mordell-Weil-Gruppe E(ℚ). Nach dem Satz von Mordell-Weil ist sie endlich erzeugt und hat die Form E(ℚ) = 𝕋 × ℤʳ. Dabei ist 𝕋 = E(ℚ)_tors die Torsionsuntergruppe und r der algebraische Rang. Jeder Punkt kann als P = n₁P₁ + … + nᵣPᵣ + Q geschrieben werden, wobei P₁,…,Pᵣ feste Erzeuger und Q aus einer endlichen Menge ist. Allgemein bezeichnet E(K)[N] die K-rationalen Punkte, deren Ordnung ein Teiler von N ist.

Der Satz von Lutz und Nagell besagt für Torsionspunkte P = (x,y) endlicher Ordnung, dass x,y ∈ ℤ gelten und entweder y = 0 ist oder y² die Diskriminante D teilt. Damit lassen sich mögliche Torsionspunkte bestimmen. Nach dem Satz von Mazur kann die Ordnung N eines Torsionspunktes über ℚ nur die Werte 1 bis 10 oder 12 annehmen. Ein entsprechender Algorithmus sucht zunächst y² | D, bestimmt die zugehörigen x und prüft nP für n = 1,…,10,12.

Elliptische Kurven können unendlich viele rationale Punkte besitzen, wenn ihr Rang nicht null ist, oder nur endlich viele, wenn sie ausschließlich eine endliche Torsionsgruppe haben. Kurven mit Geschlecht g > 1 besitzen nur endlich viele rationale Lösungen; bei g = 0 gibt es keine oder unendlich viele. Die Vermutung von Birch und Swinnerton-Dyer verknüpft den Rang mit der Ordnung der Nullstelle der L-Funktion L(E,s) bei s = 1; nach der im Artikel genannten Angabe erstreckt sich dies (Stand 2026) bis mindestens 31. Andrew Wiles bewies 1994, veröffentlicht 1995, den Modularitätssatz für spezielle elliptische Kurven und trug damit zum Beweis des Großen Fermatschen Satzes bei.

Endliche Körper, Zetafunktion und L-Funktion

Elliptische Kurven können auch über endlichen Körpern betrachtet werden. Dort gibt es nur endlich viele Punkte. Für eine Kurve E über einem Körper mit q Elementen gilt für die Punktzahl N nach Hasses Abschätzung von 1936: |N − (q + 1)| ≤ 2√q. Für eine Körpererweiterung mit qᵐ Elementen gilt allgemeiner N_m = qᵐ + 1 − αᵐ − βᵐ. Die Zahlen α und β sind die Nullstellen des charakteristischen Polynoms des Frobeniushomomorphismus φ_q. René Schoof entwickelte 1985 den ersten effizienten Algorithmus zur Berechnung von N_m; Verbesserungen folgten durch Noam Elkies 1990 und A. O. L. Atkin 1992.

Für eine über ℚ durch ganzzahlige Koeffizienten gegebene Kurve definiert die Reduktion modulo einer Primzahl p eine Kurve über 𝔽_p. Bei endlich vielen Primzahlen entstehen Singularitäten; dort liegt schlechte Reduktion vor. Für gute Reduktion ist die Hasse-Weil-Zetafunktion Z(E(𝔽_p)) = exp(Σ card[E(𝔽_{pⁿ})] Tⁿ/n) eine rationale Funktion: Z(E(𝔽_p)) = (1 − a_pT + pT²)/((1 − T)(1 − pT)).

Die L-Funktion fasst die Informationen für alle Primzahlen zusammen: L(E(ℚ),s) = ∏_p (1 − a_pp^−s + ε(p)p^{1−2s})^−1, wobei ε(p) = 1 bei guter und ε(p) = 0 bei schlechter Reduktion ist. Das Produkt konvergiert für Re(s) > 3/2. Hasse vermutete eine analytische Fortsetzung auf die gesamte komplexe Ebene und eine Funktionalgleichung zwischen L(E,s) und L(E,2−s). Diese Vermutung wurde 1999 als Konsequenz des Modularitätssatzes bewiesen.

Anwendung in der Kryptographie

Elliptische-Kurven-Kryptosysteme (ECC) sind asymmetrische beziehungsweise Public-Key-Kryptosysteme. Anders als bei symmetrischen Verfahren müssen die Kommunikationspartner keinen gemeinsamen geheimen Schlüssel kennen. Asymmetrische Verfahren verwenden Falltürfunktionen: Sie sind leicht zu berechnen, aber ohne ein geheimes Zusatzwissen praktisch schwer umkehrbar.

Bei ECC werden die Elemente einer Nachricht, etwa einzelne Bits, Punkten P einer festen elliptischen Kurve zugeordnet. Anschließend wird die Funktion P ↦ nP mit einer festen natürlichen Zahl n > 1 angewandt. Für die Sicherheit muss es schwer sein, aus (nP,P) die Zahl n zu bestimmen. Dieses Problem ist das ECDLP.

Da das ECDLP bei geeigneter Kurvenwahl als deutlich schwieriger gilt als der diskrete Logarithmus in endlichen Körpern oder die Faktorisierung ganzer Zahlen, benötigen elliptische Verfahren bei vergleichbarer Sicherheit erheblich kürzere Schlüssel als herkömmliche asymmetrische Verfahren wie RSA. Der Artikel nennt den Diffie-Hellman-Schlüsselaustausch und das Elgamal-Kryptosystem als Beispiele. Die derzeit schnellsten genannten Algorithmen sind Baby-Step-Giant-Step und Pollard-Rho; ihre Laufzeit liegt bei O(2^{n/2}), wobei n die Bitlänge der Größe des zugrunde liegenden Körpers ist. Die NSA empfahl im Januar 2009, die Internetverschlüsselung bis 2020 von RSA auf ECC umzustellen. Weitere Anwendungen elliptischer Kurven liegen bei der Faktorisierung natürlicher Zahlen.