Computer Science

CLC number: TP391

On Computing a for Order (a, n) and Its Application

关于计算 Order (a, n) 的元素a 及其应用

¹ School of Business, Xinyang University, Xinyang 464000, Henan, China (信阳学院　商学院，河南　信阳　464000)
² School of Computer and Information Technology, Xinyang Normal University, Xinyang 464000, Henan, China (信阳师范大学　计算机与信息技术学院，河南　信阳　464000)
³ School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, Hubei, China (武汉大学　国家网络安全学院，湖北　武汉　430072)

^† Corresponding author. E-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 18 June 2025

Abstract

The order $r$ of an element $a$ in the multiplicative group ${(\mathbb{Z}/n\mathbb{Z})}^{\mathrm{*}}$, denoted by $\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}(a,n)$, or $l_a(n)$ for short, plays a significant role in the period of certain pseudo-random number generators and is particularly important in Shor's quantum integer factorization algorithm, as well as in various cryptographic applications. In this paper, we present some numerical results and evidence of suitable $a$ for which $l_a(n)$ are small and relatively easy to obtain, in the light of quantum integer factorization. The results indicate that the higher the order, the larger of the number of $a$. Therefore, we propose a quantum algorithm for finding $a$ in $a^{\mathrm{2}k}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$ with $k\ge \mathrm{1}$, explicitly excluding the trivial solution $a\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$, based on Grover's search, but using fewer quantum bits. Moreover, the proposed algorithm achieves a success probability close to 1. As this type of $n$ is commonly used as an RSA modulus, once such an $a$ is found, RSA cryptographic system will be broken.

摘要

元素$a$在乘法群${(\mathbb{Z}/n\mathbb{Z})}^{\mathrm{*}}$中的阶$r$(记作$\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}(a,n)$, 或简记为$l_a(n)$)，在某些伪随机数生成器的周期中起着重要作用，并且在 Shor 量子整数分解算法以及诸多密码学应用中尤为关键。本文在量子整数分解的背景下，给出了一些数值结果与证据，表明存在一些合适的$a$，其 $l_a(n)$ 值较小且相对容易获得。结果显示，阶数越高，相应解的数量越多。基于这一观察，本文提出了一种量子算法，用于在满足$a^{\mathrm{2}k}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$的条件下(其中$k\ge \mathrm{1}$)寻找非平凡解$a$，并明确排除了平凡解$a\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$，以确保结果对因数分解具有实际意义。该算法基于改进的 Grover 搜索，所需量子比特数更少。此外，所提出的算法在理论上能以接近 1 的概率成功。当$n$被用作 RSA 模数时，一旦找到这样的$a$，RSA 密码系统就会被破坏。