Simulation of Shor Algorithm for Discrete Logarithm Problems With Comprehensive Pairs of Modulo $p$ and Order $q$
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
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 <inline-formula><tex-math notation="LaTeX">$p$</tex-math></inline-formula> and order <inline-formula><tex-math notation="LaTeX">$q$</tex-math></inline-formula>. In this article, we constructed such quantum circuits and solved DLPs for all 1860 possible pairs of <inline-formula><tex-math notation="LaTeX">$p$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$q$</tex-math></inline-formula> 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 <inline-formula><tex-math notation="LaTeX">$q$</tex-math></inline-formula>, was clarified. In addition, we generated 1015 quantum circuits for larger pairs of <inline-formula><tex-math notation="LaTeX">$p$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$q$</tex-math></inline-formula>, extrapolated the circuit sizes obtained, and compared them for <inline-formula><tex-math notation="LaTeX">$p=2048$</tex-math></inline-formula> 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 <inline-formula><tex-math notation="LaTeX">$p$</tex-math></inline-formula> is equal, we quantitatively demonstrated how much the strength of the latter decreases to the bit length of <inline-formula><tex-math notation="LaTeX">$p$</tex-math></inline-formula> 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 <inline-formula><tex-math notation="LaTeX">$p=2048$</tex-math></inline-formula> bits under Shor's algorithm is almost equivalent to that of a safe-prime group with <inline-formula><tex-math notation="LaTeX">$p=1024$</tex-math></inline-formula> bits.