Das diskrete Logarithmus-Problem

Da elliptische Kurven additiv beschrieben werden, kann das diskrete Logarithmus Problem wie folgt definiert werden:

Definition 4.1   Sei $\left( G,+\right)$ eine additiv geschriebene Gruppe, $H$ eine von einem Element erzeugte Untergruppe von $G$, d.h. $H=\left\langle h\right\rangle$. Für ein beliebiges Element $a\in G$ besteht das diskrete Logarithmus Problem (DLP) darin, zu entscheiden, ob $a\in H$, und falls ja, ein $m\in \mathbb{Z}$ zu berechnen, so daß $m\cdot h:=\underbrace{h+\ldots +h}_{m\textrm{ mal}}=a$ ist. Dieses $m$ wird als $\log _{h}a$, der Logarithmus von $a$, bezeichnet.

Wie beim Faktorisieren stellt sich bei der Berechnung von diskreten Logarithmen heraus, daß i.a. keine effizienten, d.h. in Polynomialzeit durchführbaren Algorithmen bekannt sind. Während aber für die Faktorisierung einer beliebigen Zahl grundsätzlich subexponentielle Algorithmen zur Verfügung stehen, sind subexponentielle Algorithmen zur Berechnung diskreter Logarithmen i.a. nicht bekannt. Es gibt aber Familien von Gruppen, für die aber doch subexponentielle Algorithmen bekannt sind; die multiplikativen Gruppen der endlichen Körper $\mathbb{F}_{q}$ gehören zu dieser Familie.

Die Familie der Gruppen, die durch bestimmte elliptische Kurven über endlichen Körpern gebildet werden, gehören vermutlich nicht dazu; diese bestimmten elliptischen Kurven zeichnen sich dadurch aus, gewisse Eigenschaften nicht zu haben.