Minimizing CNOT-count in quantum circuit of the extended Shor’s algorithm for ECDLP
Authors:
Open Access
- 6 December 2023
- journal article
- research article
- Published by Springer Nature in Cybersecurity
- Vol. 6 (1) , 1-27
Abstract
The elliptic curve discrete logarithm problem (ECDLP) is a popular choice for cryptosystems due to its high level of security. However, with the advent of the extended Shor’s algorithm, there is concern that ECDLP may soon be vulnerable. While the algorithm does offer hope in solving ECDLP, it is still uncertain whether it can pose a real threat in practice. From the perspective of the quantum circuits of the algorithm, this paper analyzes the feasibility of cracking ECDLP using an ion trap quantum computer with improved quantum circuits for the extended Shor’s algorithm. We give precise quantum circuits for extended Shor’s algorithm to calculate discrete logarithms on elliptic curves over prime fields, including modular subtraction, three different modular multiplication, and modular inverse. Additionally, we incorporate and improve upon windowed arithmetic in the circuits to reduce the CNOT-counts. Whereas previous studies mostly focused on minimizing the number of qubits or the depth of the circuit, we focus on minimizing the number of CNOT gates in the circuit, which greatly affects the running time of the algorithm on an ion trap quantum computer. Specifically, we begin by presenting implementations of basic arithmetic operations with the lowest known CNOT-counts, along with improved constructions for modular inverse, point addition, and windowed arithmetic. Next, we precisely estimate that, to execute the extended Shor’s algorithm with the improved circuits to factor an n-bit integer, the CNOT-count required is $$1237n^3/\log n+2n^2+n$$ . Finally, we analyze the running time and feasibility of the extended Shor’s algorithm on an ion trap quantum computer.
Keywords
Funding Information
- National Natural Science Foundation of China (61672517, 61732021)
This publication has 21 references indexed in Scilit:
- Quantum Control and Quantum Information TechnologyThe Scientific World Journal, 2013
- Quantum Circuit ArchitecturePhysical Review Letters, 2008
- Quantum Computation and Quantum InformationAmerican Journal of Physics, 2002
- Use of Elliptic Curves in Cryptography2000
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Review, 1999
- Quantum networks for elementary arithmetic operationsPhysical Review A, 1996
- Quantum Cryptanalysis of Hidden Linear Functions1995
- The Montgomery inverse and its applicationsIEEE Transactions on Computers, 1995
- Elliptic curve cryptosystemsMathematics of Computation, 1987
- Zur Theorie der abstrakten elliptischen Funktionenkörper III. Die Struktur des Meromorphismenrings. Die Riemannsche Vermutung.Journal für die reine und angewandte Mathematik (Crelles Journal), 1936