2.3 Berechnung der Addition

für elliptische Kurven über R

Im vorherigen Kapitel wurde gezeigt, daß es möglich ist, Punkte einer elliptischen Kurve zu addieren. Wie nun die genaue Berechnung dieser Addition für elliptische Kurven über R erfolgt, ist hier zu finden.

Zur Erinnerung: Elliptische Kurven über R werden durch folgende Gleichung impliziert gegeben:

mit siehe Gl.2.1.1

Wenn im weiteren von elliptischen Kurven gesprochen wird, sind die Kurven gemeint, für die obige Gleichungen gültig sind. Folgende Vereinbarung über die Schreibweise ist getroffen:
P und Q sind die Punkte, die addiert werden sollen. R ist das Ergebnis der Addition. Ein Punkt P hat die Koordinaten xP und yP, auch P(xP, yP) geschrieben.

Zur genauen Berechnung müssen nun Bleistift und Lineal aus dem vorherigen Kapitel durch genaue mathematische Formeln ersetzt werden.

Per Definition zum Ergebnis

Wenn einer der beiden Punkte P oder Q gleich O ist, dann ist das Ergebnis R der jeweils andere Punkt, da O als neutrales Element festgelegt ist.
Im Weiteren seien die Punkte ungleich O.

Geradengleichung statt Lineal

Für die Gerade durch die Punkte P und Q ist nun eine Geradengleichung zu finden. Aus der Schulmathematik ist die allgemeine Form einer Geradengleichung

g(x) = mx + b Gl.2.3.1

bekannt, m ist dabei die Steigung der Geraden und b der y-Achsen-Abschnitt.
Für die Steigung m sind drei Fälle zu unterscheiden.

  1. wenn P ¹ Q und xP ¹ xQ, berechnet sich m aus vertikalem zu horizontalem Zuwachs zwischen P und Q
    Gl.2.3.2
  2. wenn P = Q und yP ¹ 0, ist die Gerade eine Tangente und hat die Steigung m, die auch die elliptische Kurve in P hat. Die Steigung im Punkt P der elliptischen Kurve läßt sich durch einsetzen in die 1. Ableitung der Kurve
    siehe Gl.2.1.3 bestimmen.
     

    also
    Gl.2.3.3
  3. wenn xP = xQ (1. Fall) oder yP ¹ 0 (2. Fall) ist, kann die Steigung m nicht mit obigen Formeln berechnet werden, da der Nenner Null würde. In diesem Fall muß hier nicht weiter gerechnet werden, denn das Ergebnis ist O, denn es handelt sich um eine senktrechte zur x-Achse(siehe Gl.2.2.4 ).

Der y-Achsen-Abschnitt b berechnet sich in beiden Fällen gleich und läßt nach Berechnung von m durch Umstellen der Geradengleichung (Gl.2.3.1) nach b und Einsetzen eines beliebigen Punktes der Geraden berechnen.

b = y - mx Gl.2.3.4

Nachdem man die Geradengleichung bestimmt hat, sind die Schnittpunkte der elliptischen Kurve und der Geraden zu berechnen.

Schnittpunkt von Gerade und Kurve

Wie in Gl.2.2.1 entsteht eine Gleichung dritten Gerades mit drei Nullstellen.

Gl.2.3.5

Mit elementarer Algebra und den beiden bekannten Nullstellen, ergeben sich daraus recht einfache Formeln für die Koordinaten von R. Für eine genaue mathematische Berechnung sei hier [LEM98] (Kap.2, S. 42f.) hingewiesen.

xR = m2 - xP -xQ Gl.2.3.6
yR = - yP + m(xP - xR ) Gl.2.3.7

In diesen Formeln ist schon berücksichtigt, daß R der an der x-Achse gespiegelte Punkt ist.

Abb.2.3.1: Beispiel Addition

Ein Beispiel

Gegeben sind:

P = (-3,51 / 0,59)

Q = (0,78 / 2,32)

 

Und die elliptische Kurve über R mit den Koeffizienten a = -9 und b = 12, also:

E: y2 = x3 - 9x + 12

 

 

Gesucht ist der Punkt R.

Als erstes muß m berechnet werden. Da P und Q nicht gleich sind, geschieht dies mit Gl.2.3.2.

Die Koordinaten von R, also das Ergebnis errechnen sich dann mit Gl.2.3.6 und Gl.2.3.7

xR = m2 - xP -xQ = 0,1461 + 3,51 - 0,78 » 2,88
yR = - yP + m(xP - xR ) = - 0,59 + 0,3823 (-3,51 - 2,88) » -3,16

Es ist also R = (2,88/-3,16).

In diesem Beispiel sieht man, daß das Ergebnis nicht exakt ist, da z.B. die Steigung gerundet wurde. Im nächsten Kapitel wird beschrieben, wie exakte Additionen mit elliptischen Kurven möglich sind.

Zum Abschuß noch ein Applet, das die Graphen perspektivisch darstellt (s. Abb.2.2.3), damit auch Additionen von O möglich sind.

</COMMENT>

Um das nebenstehende Applet zu starten, ist auf 'Start' zu klicken. Nach kurzer Zeit erscheint ein neues Fenster mit dem Programm. Zum Beenden des Programms ist 'Stop' zu wählen. Mit 'in den Vordergrund' ist ein von anderen Fenstern verdecktes Programm wieder in den Vordergrund zu holen.

Falls es Probleme mit dem Ausführen des Applet geben sollte, ist hier Hilfe zu finden.

 

App.:2.3.1 Addition incl. O  
zum Anfang | Home
Copyright 1999 by Thomas Laubrock
Zurück zur letzen Seite nächste Seite