Quantum Circuit Optimization for Solving Discrete Logarithm of Binary Elliptic Curves Obeying the Nearest-Neighbor Constrained |
| |
| Authors: | Jianmei Liu Hong Wang Zhi Ma Qianheng Duan Yangyang Fei Xiangdong Meng |
| |
| Affiliation: | 1.State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China; (J.L.); (Q.D.); (Y.F.); (X.M.);2.Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China |
| |
| Abstract: | In this paper, we consider the optimization of the quantum circuit for discrete logarithm of binary elliptic curves under a constrained connectivity, focusing on the resource expenditure and the optimal design for quantum operations such as the addition, binary shift, multiplication, squaring, inversion, and division included in the point addition on binary elliptic curves. Based on the space-efficient quantum Karatsuba multiplication, the number of CNOTs in the circuits of inversion and division has been reduced with the help of the Steiner tree problem reduction. The optimized size of the CNOTs is related to the minimum degree of the connected graph. |
| |
| Keywords: | elliptic curve discrete logarithm quantum circuit |
|
|
