Beweis: Wir wählen uns
, wobei ein
Punkt der Ordnung ist. Ferner notieren wir mit die
Funktion, die durch
Es gilt
Sei nun
. Nach [Sem93] gilt dann die
folgende Gleichung
Gleichung (3) öffnet uns nun eine Methode zur Berechnung
des Funktionswertes . Aus (3) erhalten wir
nämlich
Seien nun
und wie folgt definiert:
Aus
Die Funktionen der letzten Zeile dieser Gleichung können durch die
folgenden Betrachtungen bestimmt werden. Sei
eine beliebige in lineare Funktion und
. Wir müssen den Wert der Funktion
an
einem Punkt bestimmen und drücken dazu diese Funktion durch die
Funktionen , aus, wobei
( aus der Definition der verwendeten elliptischen
Kurve). Wir haben
und wissen aus
[Sil86, III. §5], daß ein invariantes Differential auf
ist, d.h.
für alle . Wenn
wir nun
einführen, erhalten wir
und so
und schließlich
Also müssen wir die Werte von Funktionen der Bauart auswerten, deren Koeffizienten durch die Koordinaten der Punkte und bestimmt sind. Insgesamt haben wir solcher Punkte auszuwerten, da die Punkte dieser Menge durch dieselbe Menge ausgedrückt werden, ist die Komplexität dieser Berechnung nicht mehr als Operationen in .
Aus (4) folgt außerdem, daß die Funktionen und an regulär sind. Also benötigt insgesamt die Komplexität der Auswertung der Funktionswerte an nicht mehr als Operation in . Genauer gesagt werden die obigen Berechnungen in einer Körpererweiterung von ausgeführt, die man durch Adjungation des Punktes der Ordnung erhält, aber da diese Erweiterung höchstens Grad hat, ist der Aufwand für diese Operationen proportional zu denen in .fill
Aus Lemma 3 folgt, daß die Komplexität des diskreten Logarithmusproblems in der Gruppe nicht mehr als Operationen in beträgt. Tatsächlich müssen wir, um zu erhalten, so daß in gilt, die Werte und wie in Lemma 3 berechnen und daraus schließlich durch Rechnung in , womit wir dann den diskreten Logarithmus berechnet hätten.
Stefan Röhrich stefan@roehri.ch