Computation of the discrete logarithm on elliptic curves of trace one ? Tutorial

Security and Cryptography Laboratory,Swiss Federal Institute of Technology, CH-1015 Lausanne, SwitzerlandJean.Monnerat@epfl.chAbstract. The security of several elliptic curve cryptosystems is basedon the difficulty to compute the discrete logarithm problem. The moti-vation of using elliptic curves in cryptography is that there is no knownsub-exponential algorithm which solves the Elliptic Curve Discrete Log-arithm Problem (ECDLP) in general. However, it has been shown thatsome special curves do not possess a difficult ECDLP. In 1999, an articleof Nigel Smart provides a very efficient method for solving the ECDLPwhen the underlying elliptic curve is of trace one. In this note, we describethis method in more details and recall the mathematical background inorder to understand it.