Public key cryptography can be based on integer factorization and the discrete logarithm problem (DLP), applicable in multiplicative groups and elliptic curves. Regev’s recent quantum algorithm was initially designed for solving the integer factorization problem and was later extended to the DLP in the multiplicative group. In this article, we further extend the algorithm to address the DLP for elliptic curves. Notably, based on celebrated conjectures in Number Theory, Regev’s algorithm is asymptotically faster than Shor’s algorithm for elliptic curves. We examine the general framework of Regev’s algorithm. This preliminary analysis enables us to certify the success of the algorithm on a particular instance before running it. We prove that the algorithm naturally adapts to the multidimensional DLP. We pave the way for the implementation of Regev’s algorithm on certain NIST-listed elliptic curves. Notably, Bernstein’s Curve25519 and the deprecated Koblitz curve K-233 have small coefficients—a key feature in the implementation of Regev’s algorithm.