AN <i>O</i>(<i>m</i><SUP>2</SUP>)-DEPTH QUANTUM ALGORITHM FOR THE ELLIPTIC CURVE DISCRETE LOGARITHM PROBLEM OVER <i>GF</i>(2<i><SUP>m</SUP></i>)<i><SUP>a</SUP></i>

作     者：Maslov, Dmitri Mathew, Jimson Cheung, Donny Pradhan, Dhiraj K. 

作者机构：Univ Waterloo Dept Phys & Astron Waterloo ON N2L 3G1 Canada Natl Sci Fdn Directorate Comp & Informat Sci & Engn Arlington VA 22230 USA Univ Bristol Dept Comp Sci Bristol BS8 1UB Avon England Univ Calgary Dept Comp Sci Calgary AB T2N 1N4 Canada 

出 版 物：《QUANTUM INFORMATION & COMPUTATION》 (Quantum Inf. Comput.)

年 卷 期：2009年第9卷第7-8期

页      面：610-621页

核心收录：

学科分类：07[理学] 070201[理学-理论物理] 0702[理学-物理学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Quantum Circuits Cryptography Elliptic Curve Discrete Logarithm Problem Quantum Algorithms 

摘      要：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.