An O(m2)-depth quantum algorithm for the elliptic curve discrete logarithm problem over GF(2m)a

D. Maslov, Jimson Mathew, D. Cheung, Pradhan Dhiraj

Research output: Contribution to journalArticle (Academic Journal)peer-review

15 Citations (Scopus)

Abstract

We consider a quantum polynomial-time algorithm which solves the discrete logarithm problem for points on elliptic curves over GF(2m). 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(m2), which is an improvement over the previous bound of O(m3) derived assuming no architectural restrictions.
Translated title of the contributionAN O(m2)-DEPTH QUANTUM ALGORITHM FOR THE ELLIPTIC CURVE DISCRETE LOGARITHM PROBLEM OVER GF(2^m)
Original languageEnglish
Article number0610-0627
Pages (from-to)610-621
JournalQuantum Information and Computation
Volume9
Issue number7
Publication statusPublished - 2009

Bibliographical note

Other identifier: 2001057

Fingerprint Dive into the research topics of 'An O(m<sup>2</sup>)-depth quantum algorithm for the elliptic curve discrete logarithm problem over GF(2<sup>m</sup>)<sup>a</sup>'. Together they form a unique fingerprint.

Cite this