An O(m^2)-depth quantum algorithm for the elliptic curve discrete logarithm problem over GF(2^m)
Dmitri A Maslov, J. Mathew, D. Cheung, D.K. Pradhan · Quantum Information and Computation · 2009
We consider a quantum polynomial-time algorithm which solves the discrete logarithm problem for points on elliptic curves over $GF(2^m)$. We improve over earlier algorithms by constructing an efficient circuit for multiplying elements of binary finite fields and by representing elliptic curve points using a technique based on projective coordinates. The depth of our proposed implementation, executable in the Linear Nearest Neighbor (LNN) architecture, is $O(m^2)$, which is an improvement over the previous bound of $O(m^3)$ derived assuming no architectural restrictions.