Der Monomorphismus $\phi$

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

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

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.