On the computation of logarithms on elliptic curves

I. A. Semaev

Diskretnaya Matematika, Tome 8 (1996) no. 1, pp. 65-71.

Résumé

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.