Abstract:
The discrete logarithm problem (DLP) over finite fields, commonly used in classical cryptography, has no known polynomial-time algorithm on classical computers. However, Shor has provided its polynomial-time algorithm on quantum computers. Nevertheless, there are only few examples simulating quantum circuits that operate on general pairs of modulo p and order q. In this article, we constructed such quantum circuits and solved DLPs for all 1860 possible pairs of p and q up to 32 qubits using a quantum simulator with PRIMEHPC FX700. From this, we obtained and verified values of the success probabilities, which had previously been heuristically analyzed by Ekerå (2019). As a result, the detailed waveform shape of the success probability of Shor’s algorithm for solving the DLP, known as a periodic function of order q, was clarified. In addition, we generated 1015 quantum circuits for larger pairs of p and q, extrapolated the circuit sizes obtained, and compared them for p=2048 bits between safe-prime groups and Schnorr groups. While in classical cryptography, the cipher strength of safe-prime groups and Schnorr groups is the same if p is equal, we quantitatively demonstrated how much the strength of the latter decreases to the bit length of p in the former when using Shor’s quantum algorithm. In particular, it was experimentally and theoretically shown that when a basic adder is used in the addition circuit, the cryptographic strength of a Schnorr group with p=2048 bits under Shor’s algorithm is almost equivalent to that of a safe-prime group with p=1024 bits.