Simulation of Shor Algorithm for Discrete Logarithm Problems With Comprehensive Pairs of Modulo $p$ and Order $q$
Kaito Kishi, Junpei Yamaguchi, Tetsuya Izu, Noboru Kunihiro · IEEE Transactions on Quantum Engineering · 2025
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 paper, we constructed such quantum circuits and solved DLPs for all 1,860 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å, arXiv:1905.09084 (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. Additionally, we generated 1,015 quantum circuits for larger pairs of$p$and$q$, extrapolated the circuit sizes obtained, and compared them for$p = 2048$bits between safeprime 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.