Minimizing CNOT-count in quantum circuit of the extended Shor’s algorithm for ECDLP  

作　　者：Xia Liu Huan Yang Li Yang 

机构地区：[1]State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing,China [2]School of Cyber Security,University of Chinese Academy of Sciences,Beijing,China [3]Beijing Youzhuju Network Technology Co.,Ltd.,Beijing,China

出　　处：《Cybersecurity》2025年第1期153-179,共27页网络空间安全科学与技术(英文)

基　　金：supported by National Natural Science Foundation of China(Grant No.61672517);National Natural Science Foundation of China(Key Program,Grant No.61732021).

摘　　要：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 ofer 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 felds,including modular subtraction,three diferent modular multiplication,and modular inverse.Additionally,we incorporate and improve upon windowed arithmetic in the circuits to reduce the CNOTcounts.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 afects the running time of the algorithm on an ion trap quantum computer.Specifcally,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 is1237n^(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.

关 键 词：Elliptic curve discrete logarithm problem Extended Shor’s algorithm Quantum circuits Ion trap quantum computer 

分 类 号：O41[理学—理论物理]