Quantum Algorithm for Solving the Discrete Logarithm Problem in the Class Group of an Imaginary Quadratic Field and Security Comparison of Current Cryptosystems at the Beginning of Quantum Computer Age

摘要

In this paper, we present a quantum algorithm which solves the discrete logarithm problem in the class group of an imaginary quadratic number field. We give an accurate estimation of the qubit complexity for this algorithm. Based on this result and analog results for the factoring and the discrete logarithm problem in the point group of an elliptic curve, we compare the run-times of cryptosystems which are based on problems above. Assuming that the size of quantum computers will grow slowly, we give proposals which cryptosystem should be used if middle-size quantum computers will be built.