模p和阶q全面对的离散对数问题的Shor算法模拟
Simulation of Shor algorithm for discrete logarithm problems with comprehensive pairs of modulo p and order q
摘要 Abstract
在有限域上的离散对数问题(DLP)是经典密码学中的常用工具,但在经典计算机上尚未发现其多项式时间算法。然而,Shor提出了一种在量子计算机上解决该问题的多项式时间算法。尽管如此,目前仅存在少量针对一般模p和阶q对的量子电路仿真的例子。本文构建了此类量子电路,并利用PRIMEHPC FX700量子模拟器解决了多达32个量子比特的所有1,860对可能的p和q的DLP。通过这一工作,我们得到了并验证了成功概率的值,这些值之前曾被Eker\r{a}基于启发式方法分析过。结果表明,Shor算法解决DLP的成功概率呈现出由阶q确定的具有不对称波形的周期性。此外,我们还为更大的p和q对生成了1,015个量子电路,外推了所获得的电路规模,并比较了当p为2048位时安全素数群组与Schnorr群组之间的电路规模。虽然在经典密码学中,若p相等,则安全素数群组与Schnorr群组的加密强度相同,但我们定量地展示了当使用Shor的量子算法时,后者的强度相对于前者如何随p的比特长度降低。特别是,实验和理论研究表明,当使用ripple carry加法器时,在Shor算法下,p为2048位的Schnorr群组的加密强度几乎等同于p为1024位的安全素数群组的加密强度。
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\r{a}. As a result, we found that the success probability of Shor's algorithm for solving the DLP exhibits periodicity with an asymmetric waveform determined by the order $q$. 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 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 ripple carry 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.