Der Monomorphismus $\phi $

Wir definieren mit einem festen Punkt $R \in \langle P \rangle
\setminus \{\mathcal{O}\}$:

\begin{displaymath}
\begin{array}{cccl}
\phi \colon & \langle P \rangle & \longr...
..._Q}{d t f_Q} (R)\\
& \mathcal{O}& \longmapsto & 0.
\end{array}\end{displaymath}

Für $\vert\langle P \rangle \vert = \mathop{\rm char} \nolimits (\mathbbm{F}_q)$ ist diese Abbildung wohldefiniert (Beweis folgt in Lemma 2), in diesem Fall ist $\phi $ ein injektiver Homomorphismus.

$\phi(Q) = \frac{d f_Q}{d t f_Q} (R)$ läßt sich durch eine rekursive Zerlegung berechnen (Details siehe Beweis von Lemma 3), bei dieser Zerlegung mit Tiefe $O(\log p)$ treten pro Zerlegungsschritt nur konstant viele neue Elemente auf, wobei die Berechnungen in einer Körpererweiterung von $\mathbbm{F}_q$ von maximal Grad 3 durchgeführt werden können.

Somit läßt sich $\phi $ in $O(\log p)$ Schritten berechnen, d.h. der Aufwand zur Berechnung des diskreten Logarithmus ist in unserem Fall polynomial in der Bitlänge des zugrundeliegenden Körpers.



Stefan Röhrich stefan@roehri.ch
2002-04-23 21:32:56