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

作者：Maslov Dmitri^*; Mathew Jimson; Cheung Donny; Pradhan Dhiraj K

来源：Quantum Information & Computation, 2009, 9(7-8): 610-621.

• 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.

• 出版日期2009-7
• 单位国家自然科学基金委员会