2023/03/12 by Hyeonhak Kim, Kim, Hyeonhak, Seokhie Hong +1
Computer Science · #Coding theory and cryptography #Cryptography and Data Security #Cryptography and Residue Arithmetic #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2303.06570
openalex publication_date 2023/03/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In previous research, quantum resources were concretely estimated for solving Elliptic Curve Discrete Logarithm Problem(ECDLP). In [1], the quantum algorithm was optimized for the binary elliptic curves and the main optimization target was the number of the logical qubits. The division algorithm was mainly optimized in [1] since every ancillary qubit is used in the division algorithm. In this paper, we suggest a new quantum division algorithm on the binary field which uses a smaller number of qubits. For elements in a field of 2n, we can save \lceil n/2 \rceil - 1 qubits instead of using 8n2+4n-12+(16n-8)\lfloorlog(n)\rfloor more Toffoli gates, which leads to a more space-efficient quantum algorithm for binary elliptic curves.