Abstract
We estimate the number of physical qubits and execution time by decomposing an implementation of Shor's algorithm for elliptic curve discrete logarithms into universal gate units at the logical level when surface codes are used. We herein also present modified quantum circuits for elliptic curve discrete logarithms and compare our results with those of the original quantum circuit implementations at the physical level. Through the analysis, we show that the use of more logical qubits in quantum algorithms does not always lead to the use of more physical qubits. We assumed using rotated surface code and logical qubits with all-to-all connectivity. The number of physical qubits and execution time are expressed in terms of bit length, physical gate error rate, and probability of algorithm failure. In addition, we compare our results with the number of physical qubits and execution time of Shor's factoring algorithm to assess the risk of attack by quantum computers in RSA and elliptic curve cryptography.