A Las Vegas Algorithm to Solve the Elliptic Curve Discrete Logarithm Problem

Abstract

In this paper, we describe a new Las Vegas algorithm to solve the elliptic curve discrete logarithm problem. The algorithm depends on a property of the group of rational points on an elliptic curve and is thus not a generic algorithm. The algorithm that we describe has some similarities with the most powerful index-calculus algorithm for the discrete logarithm problem over a finite field. The algorithm has no restriction on the finite field over which the elliptic curve is defined.