Diskrete Logarithmen

Definition 2 (DLOG)   Das Problem, aus zwei gegebenen Punkten $P, Q \in E(\mathbbm{F}_q)$ ein $n$ zu bestimmen, so daß $Q = nP$ (falls so ein $n$ existiert), wird als das Problem des diskreten Logarithmus oder DLOG (in $E(\mathbbm{F}_q)$ zur Basis $P$) bezeichnet, Schreibweise: $n = \mathop{\rm dlog} \nolimits _P(Q)$.

Die Bezeichnung ,,diskreter Logarithmus`` kommt von der Bezeichnung desselben Problems in multiplikativ geschriebenen Gruppen, da es sich nur um eine andere Schreibweise der Gruppenverknüpfung handelt (abelsche Gruppen werden zumeist additiv geschrieben), verwendet man auch sinnvollerweise diese Bezeichnung, zumal die ,,optisch`` näherliegende Bezeichnung ,,diskretes Teilen`` o.ä. nicht an ein schwieriges Problem denken läßt.

Im allgemeinen ist bis jetzt zur Lösung des Problems des diskreten Logarithmus auf elliptischen Kurven kein effizientes Verfahren bekannt. In einigen Spezialfällen kennt man aber sehr wohl Verfahren, von denen hier eines untersucht werden soll, das in [Sem98] beschrieben wird. Auf diesem Artikel beruht auch diese Ausarbeitung, weitere Fälle werden z.B. in [MOV93] behandelt, und bei der Benutzung eines Kryptoverfahrens, das auf dem DLOG auf elliptischen Kurven beruht, ist darauf zu achten, daß man nicht in einen dieser Spezialfälle gerät.

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