Abstract:
We consider the problem of solving an exponential equation over
a cyclic subgroup of order $m$ of the group $E$ of points
of an elliptic curve over the finite field $F_q$. We prove that if $F_{q_1}$
is a minimal extension of $F_q$ such that the subgroup of the points rational
over $F_{q_1}$ of the group $E$ contains a subgroup isomorphic to
$\Z/m\times\Z/m$, then the complexity of solving the equation
mentioned above is no greater than the complexity of computing logarithms
in the field $F_{q_1}$ or the complexity of $O(\ln m)$ arithmetic operations
in that field. Thus, the computing of logarithms on elliptic curves is reduced
to the computing of logarithms in a finite field. By a different approach,
this result was obtained by Menezes, Okamoto, and Vanstone.
Fulltext:
PDF file (748 kB)