A quantum circuit to find discrete logarithms on ordinary binary\n elliptic curves in depth O(log² n)

2013/06/05 by Martin Roetteler, Roetteler, Martin, Rainer Steinwandt +1 · 1 citation
Computer Science · #Coding theory and cryptography #Cryptography and Data Security #Cryptography and Residue Arithmetic #Data Structures and Algorithms (cs.DS) #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #FOS: Physical sciences #Internet Traffic Analysis and Secure E-voting #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.1306.1161

openalex publication_date 2013/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Improving over an earlier construction by Kaye and Zalka, Maslov et al.\ndescribe an implementation of Shor's algorithm which can solve the discrete\nlogarithm problem on binary elliptic curves in quadratic depth O(n²). In this\npaper we show that discrete logarithms on such curves can be found with a\nquantum circuit of depth O(log² n). As technical tools we introduce quantum\ncircuits for GF(2ⁿ) multiplication in depth O(log n) and for GF(2ⁿ) inversion\nin depth O(log² n).\n

Citations

• Shor's algorithm on a nearest-neighbor machine
• Fast parallel circuits for the quantum Fourier transform

Cited by

• Asymptotic yet practical optimization of quantum circuits implementing GF(2^m) multiplication and division operations

Related

• Improved quantum circuits for elliptic curve discrete logarithms
• Shor's discrete logarithm quantum algorithm for elliptic curves
• Quantum resource estimates for computing elliptic curve discrete logarithms
• New Space-Efficient Quantum Algorithm for Binary Elliptic Curves using the Optimized Division Algorithm
• Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost