Computation of the discrete logarithm on elliptic curves of trace one

The security of several elliptic curve cryptosystems is based on the difficulty to compute the discrete logarithm problem. The motivation of using elliptic curves in cryptography is that there is no known sub-exponential algorithm which solves the Elliptic Curve Discrete Logarithm Problem (ECDLP) in general. However, it has been shown that some special curves do not possess a difficult ECDLP. In 1999, an article of Nigel Smart provides a very efficient method for solving the ECDLP when the underlying elliptic curve is of trace one. In this note, we describe this method in more details and recall the mathematical background in order to understand it.