Shor’s quantum algorithm can solve the factorization problem and the elliptic curve discrete logarithm problem (ECDLP) in polynomial time. Due to the physical barrier for realizing large-scale reliable quantum computer, designs of concrete quantum circuits and their resource estimates have been actively discussed. In this paper, we focus on the case of the binary ECDLP. In particular, since the quantum resource for solving the binary ECDLP heavily depends on the quantum inversion algorithm over \(\mathbb F_{2^n}\) , we summarize the known quantum inversion algorithms and compare the quantum resource.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Shor’s Quantum Algorithm for Solving the Binary ECDLP: A Survey

  • Ren Taguchi,
  • Atsushi Takayasu

摘要

Shor’s quantum algorithm can solve the factorization problem and the elliptic curve discrete logarithm problem (ECDLP) in polynomial time. Due to the physical barrier for realizing large-scale reliable quantum computer, designs of concrete quantum circuits and their resource estimates have been actively discussed. In this paper, we focus on the case of the binary ECDLP. In particular, since the quantum resource for solving the binary ECDLP heavily depends on the quantum inversion algorithm over \(\mathbb F_{2^n}\) , we summarize the known quantum inversion algorithms and compare the quantum resource.