© Wuhan University 2026

0 Introduction

Quantum computing is an exciting technology at the intersection of computer science and physics, leveraging the unique properties of quantum mechanics to increase the speed of classical computational operations in certain cases. Advances in quantum computing present a serious challenge to the existing public-key cryptosystems, as schemes such as Rivest-Shamir-Adleman (RSA) and ELGamal can be efficiently broken by Shor's algorithm ^[1-2]. Therefore, studying cryptanalysis in the context of quantum computing has become increasingly important^[3].Because the RSA cryptosystem is widely used in industry and government, fast cracking RSA has become an important research direction of modern cryptanalysis. The security of RSA depends on the intractability of the integer factorization problem. Therefore, the core approach to attacking RSA is to design efficient algorithms for factoring its modulus.

One of the most groundbreaking developments in integer factorization occurred in 1994, when Shor discovered a quantum algorithm capable of factoring integers in polynomial time^[1-2]. If implemented on a practical quantum computer with several thousand quantum bits, Shor's algorithm can factor integers in probabilistic quantum polynomial time $O\left({(\mathrm{l}\mathrm{o}\mathrm{g}n)}^{\mathrm{3}}\right)$, representing a significant improvement over the classical number field sieve algorithm^[4], whose runtime is sub-exponential runtime of the form $O(\mathrm{e}\mathrm{x}\mathrm{p}\left(c{(\mathrm{l}\mathrm{o}\mathrm{g}n)}^{\mathrm{1}/\mathrm{3}}{(\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{l}\mathrm{o}\mathrm{g}n)}^{\mathrm{2}/\mathrm{3}})\right)$ where $c={(\mathrm{64}/\mathrm{9})}^{\mathrm{1}/\mathrm{3}}\approx \mathrm{1.92}$. This discovery poses a direct threat to the security of RSA encryption. Although Shor's algorithm operates on a classical computer, its remarkable efficiency stems from a key quantum subroutine. In the following sections, we present a simplified version of this algorithm as shown in Fig. 1, where r is the order 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.

Fig.1 Simplified flowchart of Shor's algorithm

The emergence of Shor's algorithm has injected new vitality into the research of quantum computing, which has provided a driving force to promote quantum computing research in the last twenty years^[5-12]. Current research on quantum factoring mainly focuses on improved or compiled versions of Shor's algorithm, using different techniques that have been proposed and studied. In a word, there are two important research directions in quantum integer factorization. On the one hand, people try to build a (practical) quantum computer, or even other types of physical computers, in order to implement the full version or compiled version of the Shor's algorithm ^[13-18]. On the other hand, people try to improve, modify and simplify Shor's original algorithm, or even invent new quantum factoring algorithms to be run on quantum computers with fewer quantum bits^[19-24]. Ref. [23] proposed a compilied (simplified) and optimized version of Shor's algorithm by computing just the case for $\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}(a,n)=\mathrm{2}$, as this is the simplest possible order for the algorithm to be used to factor $n$, which only need two qubits.

So far, there are no quantum computers yet that capable of running Shor's algorithm on the large semiprimes n currently used in RSA encryption algorithms. Simulating Grover's algorithm has been achieved. Therefore, from another perspective, we propose an algorithm based on Grover's algorithm, which finds $a$ satisfying $a^{\mathrm{2}k}\equiv$ $\mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$ while using fewer qubits.

The organization of the paper is as follows. In Section 1, we demonstrate through computational examples that finding a suitable $a$ such that $l_a(n)=\mathrm{2}$ holds is computationally as difficult as the Integer Factorization Problem the modulus $n(\mathrm{I}\mathrm{F}\mathrm{P}(n))$, that is,

Computing $a$ such that $l_a(n)=\mathrm{2}\iff \mathrm{I}\mathrm{F}\mathrm{P}(n).$

On the other hand, we shall look for some more suitable $a$ for high orders, that is, $l_a(n)=\mathrm{2}k,k>\mathrm{1}$. In Section 1, our results show that the higher the order, the greater the number of $a$. Therefore, from another perspective, instead of directly attempting to find $l_a(n)$, we aim to identify a suitable $a$ such that $a^{\mathrm{2}k}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$. 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}$ based on Grover's search^[25] in Section 2. The conclusion is given in Section 3.

1 Computational Evidence for Suitable Values of a

In this section, we give some numerical computations and pieces of evidences of suitable $a$ for which $l_a(n)$ are small and relatively easy to obtain, in the light of quantum integer factorization.

Firstly, it is evident that in the computation of $l_a(n)=\mathrm{2}$ (i.e., $\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}(a,n)=\mathrm{2}$ ), the task will be significantly easy for a quantum computer if the period $r$ is short, in particular, $r=\mathrm{2}$ is the shortest possible order one can expect^[19].

For $a^{\mathrm{2}}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$, if the prime factorization of $n=pq$ is known, then $a$ can be found by computing $a\equiv \pm p{p}_q\pm q{q}_p(\mathrm{m}\mathrm{o}\mathrm{d}n)$, where

$p_q\equiv \mathrm{1}/p(\mathrm{m}\mathrm{o}\mathrm{d}q),q_p\equiv \mathrm{1}/q(\mathrm{m}\mathrm{o}\mathrm{d}p)$

For example, let $n=\mathrm{221}=\mathrm{13}\times \mathrm{17}$. Then we have

$a_{\mathrm{1}}\equiv p{p}_q+q{q}_p=\mathrm{13}\times \mathrm{4}+\mathrm{17}\times \mathrm{10}=\mathrm{222}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{221})$

$a_{\mathrm{2}}\equiv p{p}_q-q{q}_p=\mathrm{13}\times \mathrm{4}-\mathrm{17}\times \mathrm{10}=-\mathrm{118}\equiv \mathrm{103}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{221})$

$a_{\mathrm{3}}\equiv -p{p}_q+q{q}_p=-\mathrm{13}\times \mathrm{4}+\mathrm{17}\times \mathrm{10}=\mathrm{118}\equiv -a_{\mathrm{2}}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{221})$

$a_{\mathrm{4}}\equiv -p{p}_q-q{q}_p=-\mathrm{13}\times \mathrm{4}-\mathrm{17}\times \mathrm{10}=-\mathrm{222}\equiv -a_{\mathrm{1}}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{221})$

$\mathrm{S}\mathrm{o},a=\{\pm \mathrm{1},\pm \mathrm{118}\}.\mathrm{C}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{l}\mathrm{y},a=\pm \mathrm{1}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{a}\mathrm{l}.\mathrm{T}\mathrm{h}\mathrm{u}\mathrm{s},\mathrm{g}\mathrm{c}\mathrm{d}(\pm \mathrm{118}\pm \mathrm{1},n)=\{\mathrm{13,17}\}.$

For $n=\mathrm{R}\mathrm{S}\mathrm{A}-\mathrm{768}$ (a number with 232 digits and 768 bits), since we know its prime factorization, we get

$a_{\mathrm{1}}\equiv p{p}_q+q{q}_p\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$

$a_{\mathrm{2}}\equiv p{p}_q-a_{\mathrm{2}}\equiv p{p}_q-\mathrm{1}\mathrm{029}\mathrm{031}\mathrm{793}\mathrm{302}\mathrm{493}\mathrm{258}\mathrm{003}\mathrm{488}\mathrm{818}\mathrm{376}\mathrm{905}\mathrm{875}\mathrm{264}\mathrm{575}\mathrm{120}\mathrm{178}\mathrm{567}\mathrm{995}\mathrm{715}\mathrm{921}\mathrm{117}\mathrm{383}\mathrm{374}\mathrm{063}\mathrm{780}\mathrm{955}\mathrm{476}\mathrm{265}\mathrm{714}\mathrm{655}\mathrm{965}\mathrm{556}\mathrm{097}\mathrm{487}\mathrm{715}\mathrm{509}\mathrm{708}\mathrm{453}\mathrm{134}\mathrm{212}\mathrm{472}\mathrm{071}\mathrm{241}\mathrm{551}\mathrm{710}\mathrm{737}\mathrm{667}\mathrm{646}\mathrm{125}\mathrm{017}\mathrm{671}\mathrm{995}\mathrm{537}\mathrm{319}\mathrm{749}\mathrm{739}\mathrm{035}\mathrm{045}\mathrm{343}\mathrm{586}\mathrm{527}\mathrm{599}\mathrm{466}\mathrm{828}\mathrm{935}\mathrm{082}\mathrm{557}\mathrm{618}\mathrm{400}\mathrm{047}\mathrm{627}\mathrm{481}\mathrm{255}\mathrm{809}\mathrm{299}\mathrm{529}\mathrm{939}(\mathrm{m}\mathrm{o}\mathrm{d}n),$

$a_{\mathrm{3}}\equiv -p{p}_q+q{q}_p\equiv \mathrm{201}\mathrm{154}\mathrm{891}\mathrm{227}\mathrm{624}\mathrm{497}\mathrm{127}\mathrm{006}\mathrm{140}\mathrm{008}\mathrm{056}\mathrm{845}\mathrm{508}\mathrm{278}\mathrm{449}\mathrm{416}\mathrm{766}\mathrm{796}\mathrm{481}\mathrm{401}\mathrm{334}\mathrm{768}\mathrm{352}\mathrm{336}\mathrm{726}\mathrm{308}\mathrm{181}\mathrm{253}\mathrm{030}\mathrm{546}\mathrm{234}\mathrm{230}\mathrm{371}\mathrm{902}\mathrm{240}\mathrm{965}\mathrm{234}\mathrm{320}\mathrm{929}\mathrm{633}\mathrm{453}\mathrm{121}\mathrm{315}\mathrm{774}\mathrm{592}\mathrm{716}\mathrm{063}\mathrm{902}\mathrm{143}\mathrm{490}\mathrm{245}\mathrm{030}\mathrm{584}\mathrm{823}\mathrm{163}\mathrm{722}\mathrm{635}\mathrm{383}\mathrm{870}\mathrm{725}\mathrm{074}\mathrm{621}\mathrm{773}\mathrm{650}\mathrm{339}\mathrm{655}\mathrm{236}\mathrm{462}\mathrm{265}\mathrm{303}\mathrm{792}\mathrm{116}\mathrm{204}\mathrm{047}\mathrm{602}\mathrm{613}\mathrm{474}(\mathrm{m}\mathrm{o}\mathrm{d}n)\equiv -a_{\mathrm{2}}(\mathrm{m}\mathrm{o}\mathrm{d}n),$

$a_{\mathrm{4}}\equiv -p{p}_q-q{q}_p\equiv -a_{\mathrm{1}}\equiv -\mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$

Thus,

$a=\pm \mathrm{1}=\pm \mathrm{201}\mathrm{154}\mathrm{891}\mathrm{227}\mathrm{624}\mathrm{497}\mathrm{127}\mathrm{006}\mathrm{140}\mathrm{008}\mathrm{056}\mathrm{845}\mathrm{508}\mathrm{278}\mathrm{449}\mathrm{416}\mathrm{766}\mathrm{796}\mathrm{481}\mathrm{401}\mathrm{334}\mathrm{768}\mathrm{352}\mathrm{336}\mathrm{726}\mathrm{308}\mathrm{181}\mathrm{253}\mathrm{030}\mathrm{546}\mathrm{234}\mathrm{230}\mathrm{371}\mathrm{902}\mathrm{240}\mathrm{965}\mathrm{234}\mathrm{320}\mathrm{929}\mathrm{633}\mathrm{453}\mathrm{121}\mathrm{315}\mathrm{774}\mathrm{592}\mathrm{716}\mathrm{063}\mathrm{902}\mathrm{143}\mathrm{490}\mathrm{245}\mathrm{030}\mathrm{584}\mathrm{823}\mathrm{163}\mathrm{722}\mathrm{635}\mathrm{383}\mathrm{870}\mathrm{725}\mathrm{074}\mathrm{621}\mathrm{773}\mathrm{650}\mathrm{339}\mathrm{655}\mathrm{236}\mathrm{462}\mathrm{265}\mathrm{303}\mathrm{792}\mathrm{116}\mathrm{204}\mathrm{047}\mathrm{602}\mathrm{613}\mathrm{474}.$

In Table 1, we list the values of a satisfying $a^{\mathrm{2}}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$, when $n$ is a factorized RSA modulus.

Proposition 1   Computing $a$ such that $l_a(n)=\mathrm{2}\iff \mathrm{I}\mathrm{F}\mathrm{P}(n).$

Proof   Because we compute $a$ such that $l_a(n)=\mathrm{2}$, that is, we obtain $a$ satisfying $a^{\mathrm{2}}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$.

So we can compute $\mathrm{g}\mathrm{c}\mathrm{d}(a\pm \mathrm{1},n)=(p,q)$, that is, we obtain the factors of $n$.

Since $n=pq$ with $p$ and $q$ two distinct prime numbers, then $a$ can be obtained by computing $a\equiv \pm p{p}_q\pm q{q}_p(\mathrm{m}\mathrm{o}\mathrm{d}n)$, where

$p_q\equiv \mathrm{1}/p(\mathrm{m}\mathrm{o}\mathrm{d}q),q_p\equiv \mathrm{1}/q(\mathrm{m}\mathrm{o}\mathrm{d}p).$

Thus, the two non-trivial solutions are $\pm a\mathrm{m}\mathrm{o}\mathrm{d}n$, and the two trivial solutions are $\pm \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}n$.That is, we obtain $a$ such that $l_a(n)=\mathrm{2}$.

Then we shall present some numerical evidences of suitable $a$ such that $l_a(n)=\mathrm{2}k$ with $k>\mathrm{1}$, since there should be more numbers of $a$ in such cases rather than just two $a$ in $a^{\mathrm{2}}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$.

We give some computation evidences of different $a$ for certain high order $l_a(n)$; note that we shall only consider the case when $l_a(n)=\mathrm{2}k$ with $k>\mathrm{1}$, since odd orders are not useful in quantum integer factorization.

Let $n=\mathrm{221}$, then for different possible with $k>\mathrm{1}$, we get the corresponding $a$ and the number of $a$ (see Table 2).

As can be observed, as the value of $r$ increases, the corresponding number of a also increases, but it dose not grow in a linear manner.

For $n=\mathrm{391}$, we have the result of Table 3.

This also shows that as the value of $r$ increases, the number of $a$ also increases. Compared with the case $r=\mathrm{2}$, there are two nontrivial values for $a$. However, for instance, when $r=\mathrm{176}$, there are a total of 160 values of $a$ that satisfy the condition $a^{\mathrm{176}}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{391})$.

In short, the above computing results indicted that the higher the order, the larger the number of $a$.

2 A Quantum Algorithm for Breaking RSA

2.1 The New Algorithm

Through some numerical computations and pieces of evidences of suitable $a$ for which $l_a(n)$ is small and relatively easy to obtain, in Section 1, in the light of quantum integer factorization, we find that the higher the order, the larger the number of $a$. Therefore, from a different perspective, rather than attempting to find the order $r$ of $a\mathrm{m}\mathrm{o}\mathrm{d}n$, we aim to find a suitable value of a such that $a^{\mathrm{2}k}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$. To avoid ambiguity, we explicitly exclude the trivial solution $a\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$, since only nontrivial solutions are useful for the factorization of $n$. Therefore, in this section, we present 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}$ based on Grover's search as follows.

Algorithm 1 This algorithm aims to find a solution $a$ in congruence $a^{\mathrm{2}k}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$ with $k\ge \mathrm{1}$, so that one can compute $\mathrm{g}\mathrm{c}\mathrm{d}\left(a^k\pm \mathrm{1},n\right)=(p,q)$ in order to factor $n=pq$.

Step 1   Find a number $q$, a power of 2 , say ${\mathrm{2}}^t$, such that $t=\lceil \mathrm{l}\mathrm{o}\mathrm{g}\frac{n}{\mathrm{2}}\rceil$.

Step 2   Initialize the two quantum registers, Reg1 and Reg2, to the all-zero state: $|{\Psi }_{\mathrm{0}}〉=|\mathrm{0}〉|\mathrm{0}〉$.

Step 3   Perform a Hadamard transform on Reg1, we get

$H:|{\Psi }_{\mathrm{0}}〉\to |{\Psi }_{\mathrm{1}}〉=\frac{\mathrm{1}}{\sqrt[]{q}}{\displaystyle \sum _{a=\mathrm{0}}^{q-\mathrm{1}}} |a〉|\mathrm{0}〉.$

Step 4   Perform the modular exponentiations $U_f$ on Reg2, we get

$U_f:|{\Psi }_{\mathrm{1}}〉\to |{\Psi }_{\mathrm{2}}〉=\frac{\mathrm{1}}{\sqrt[]{q}}{\displaystyle \sum _{a=\mathrm{0}}^{q-\mathrm{1}}} |a〉|a^{\mathrm{2}k}(\mathrm{m}\mathrm{o}\mathrm{d}n)〉,$

where $U_f:|x〉|y〉\to |x〉|y\oplus f(x)〉,f(x)=x^{\mathrm{2}k}(\mathrm{m}\mathrm{o}\mathrm{d}n).$

Step 5   Repeat the following steps $O(\sqrt[]{q})$ times.

Step 5-1   Perform a conditional phase shift $U_{O\text{'}}$ on Reg2, with $|\mathrm{1}〉$ receiving a phase shift of $-$1 , at the same time perform a conditional phase shift $U_{O\text{'}\text{'}}$ on Reg1, with $|\mathrm{1}〉$ receiving a phase shift of $-$1 , thus

$U_{O^{\text{'}}}{U}_{O^{\text{'}\text{'}}}:|{\Psi }_{\mathrm{2}}〉\to |{\Psi }_{\mathrm{3}}〉$

$=\frac{\mathrm{1}}{\sqrt[]{q}}{\displaystyle \sum _{a=\mathrm{0}}^{q-\mathrm{1}}} {(-\mathrm{1})}^{{\delta }_{\mathrm{1},a}}{(-\mathrm{1})}^{{\delta }_{\mathrm{1},a^{\mathrm{2}k}\mathrm{m}\mathrm{o}\mathrm{d}n}}|a〉|a^{\mathrm{2}k}(\mathrm{m}\mathrm{o}\mathrm{d}n)〉.$

Suppose that the number of solutions of the function $a^{\mathrm{2}k}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$ is $m^{\text{'}}$ , and these solutions are $\left\{a_{\mathrm{1}},a_{\mathrm{2}},\cdots ,a_{m^{\text{'}}}\right\}.$ $U_{O^{\text{'}}}$ denoted the operator $U_{O^{\text{'}}}=I-\mathrm{2}{\displaystyle \sum _{i=\mathrm{1}}^{m^{\text{'}}}}|a_i〉〈a_i|$, and the definition of function $\delta$ is as follows,

${\delta }_{\mathrm{1},a^{\mathrm{2}k}\mathrm{m}\mathrm{o}\mathrm{d}n}:=\{\begin{array}{ll}\mathrm{1},& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}{a}^{\mathrm{2}k}\mathrm{m}\mathrm{o}\mathrm{d}n\equiv \mathrm{1},\\ \mathrm{0},& \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}{a}^{\mathrm{2}k}\mathrm{m}\mathrm{o}\mathrm{d}n\not\equiv \mathrm{1}.\end{array}$

$U_{O\text{'}\text{'}}$ denoted the operator $U_{O"}=I-\mathrm{2}|\mathrm{1}〉〈\mathrm{1}|$.

Step 5-2   Perform the unitary operation $U$ on Reg2, where $U:|a〉|b〉\to |a〉|b\oplus a^{\mathrm{2}k}(\mathrm{m}\mathrm{o}\mathrm{d}n)〉$, obtaining

$U:|{\Psi }_{\mathrm{3}}〉\to |{\Psi }_{\mathrm{4}}〉=\frac{\mathrm{1}}{\sqrt[]{q}}{\displaystyle \sum _{a=\mathrm{0}}^{q-\mathrm{1}}} {(-\mathrm{1})}^{{\delta }_{\mathrm{1},a}}{(-\mathrm{1})}^{{\delta }_{\mathrm{1},a^{\mathrm{2}k}\mathrm{m}\mathrm{o}\mathrm{d}n}}|a〉|\mathrm{0}〉.$

Step 5-3   Perform a Hadamard transform on Reg1.

Step 5-4   Perform a conditional phase shift on Reg1, with every computational basis state expect ${|\mathrm{0}〉}^{\otimes t}$ receiving a phase shift of $-$1.

Step 5-5   Perform a Hadamard transform on Reg1.

Step 6   Measure Reg1. Suppose the state $|c〉$ has been observed. In fact, the observed $c$ satisfying $c^{\mathrm{2}k}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$ with $k\ge \mathrm{1}$ has a higher probability of being close to 1.

2.2 Algorithm Analysis

The new algorithm has the following properties:

1) The complexity of the algorithm depends on the number of iterations, requiring $O(\sqrt[]{q})$ operations. It is only a quadratic speed up algorithm compared with

classical algorithm.

2) The success probability of the algorithm also depends on the number of iterations. Ref. [25] has shown that the upper bound on the required number of iterations is

$R\le \lceil \frac{\mathrm{\pi }}{\mathrm{4}}\sqrt[]{\frac{N}{M}}\rceil ,$

where$N$ is the total number of a search space, $M$ is the number of the solutions of the search problem. That is, in the algorithm, $R=O(\sqrt[]{q})$. Grover iterations must be performed in order to obtain a solution to the congruence equation $a^{\mathrm{2}k}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n),k\ge \mathrm{1}$, with the success probability closed to 1.

3) Compared with Shor's original algorithm which chooses $q$ satisfying $n^{\mathrm{2}}\le q={\mathrm{2}}^t<\mathrm{2}{n}^{\mathrm{2}}$, this algorithm chooses $q$ satisfying $\lceil \frac{n}{\mathrm{2}}\rceil <q={\mathrm{2}}^t<n$ with $t=\lceil \mathrm{l}\mathrm{o}\mathrm{g}\frac{n}{\mathrm{2}}\rceil$. So the algorithm requires $\mathrm{3}\lceil \mathrm{l}\mathrm{o}\mathrm{g}\frac{n}{\mathrm{2}}\rceil$ qubits, and Shor's algorithm for breaking RSA requires $\mathrm{3}\lceil \mathrm{l}\mathrm{o}\mathrm{g}n\rceil$ qubits. Obviously $\mathrm{3}\lceil \mathrm{l}\mathrm{o}\mathrm{g}\frac{n}{\mathrm{2}}\rceil <\mathrm{3}\lceil \mathrm{l}\mathrm{o}\mathrm{g}n\rceil$, which indicates that the proposed approach significantly reduces the number of required qubits.

4) Shor's original algorithm tried to fix $a$ and find the smallest $r$ satisfying $a^r\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$ which chooses $q^{\text{'}}$ satisfying $n^{\mathrm{2}}\le q^{\text{'}}={\mathrm{2}}^t<\mathrm{2}{n}^{\mathrm{2}}$, with the time complexity $O\left(\sqrt[]{q^{\text{'}}}\right)$. Whereas in the algorithm, we try to find a suitable $a$, such that $a^{\mathrm{2}k}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$ with $k\ge \mathrm{1}$. The most significant advantage of the algorithm is that it uses fewer quantum bits, which will be helpful for building a quantum computer with fewer quantum bits, and that in turn is relatively easy to build compared to a quantum computer with more quantum bits.

5) Once the $a$ satisfying $a^{\mathrm{2}k}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$ with $k\ge \mathrm{1}$ is found, one can compute $\mathrm{g}\mathrm{c}\mathrm{d}\left(a^k\pm \mathrm{1},n\right)=(p,q)$, provided that $n=pq$ with $p$ and $q$ prime. This can be used to break the famous and widely used RSA cryptographic system.

2.3 Example

We give a complete example, explicitly showing each computational steps of the algorithm.

Example 1 Let $n=\mathrm{15},k=\mathrm{1}$, that is, we can find a solution $a$ satisfying $a^{\mathrm{2}}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{15})$.

Step 1   Find a number $q$, a power of 2, say ${\mathrm{2}}^t$, such that $t=\lceil \mathrm{l}\mathrm{o}\mathrm{g}\frac{\mathrm{15}}{\mathrm{2}}\rceil =\mathrm{3}$.

Step 2   Initialize the two quantum registers, Reg1 and Reg2 with zeroes $|{\Psi }_{\mathrm{0}}〉=|\mathrm{0}〉|\mathrm{0}〉$.

Step 3   Perform a Hadamard transform on Reg1, we get

$H:|{\Psi }_{\mathrm{0}}〉\to |{\Psi }_{\mathrm{1}}〉=\frac{\mathrm{1}}{\sqrt[]{\mathrm{8}}}{\displaystyle \sum _{a=\mathrm{0}}^{\mathrm{7}}}|a〉|\mathrm{0}〉 .$

Step 4   Perform the modular exponentiations $U_f$ on Reg2, we get

$U_f:|{\Psi }_{\mathrm{1}}〉\to |{\Psi }_{\mathrm{2}}〉$

$=\frac{\mathrm{1}}{\sqrt[]{\mathrm{8}}}{\displaystyle \sum _{a=\mathrm{0}}^{\mathrm{7}}} |a〉|a^{\mathrm{2}}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{15})〉$

$=\frac{\mathrm{1}}{\sqrt[]{\mathrm{8}}}(|\mathrm{0}〉|\mathrm{0}〉+|\mathrm{1}〉|\mathrm{1}〉+|\mathrm{2}〉|\mathrm{4}〉+|\mathrm{3}〉|\mathrm{9}〉$

$+|\mathrm{4}〉|\mathrm{1}〉+|\mathrm{5}〉|\mathrm{10}〉+|\mathrm{6}〉|\mathrm{6}〉+|\mathrm{7}〉|\mathrm{4}〉),$

where $U_f:|x〉|y〉\to |x〉|y\oplus f(x)〉,f(x)=x^{\mathrm{2}}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{15}).$

Step 5   Repeat the following steps 2 times.

Step 5-1   Perform a conditional phase shift $U_{O\text{'}}$ on Reg2, with $|\mathrm{1}〉$ receiving a phase shift of $-$1, and at the same time perform a conditional phase shift $U_{O\text{'}\text{'}}$ on Reg1, with $|\mathrm{1}〉$ receiving a phase shift of $-$1 , thus

$U_{O^{\text{'}}}{U}_{O^{\text{'}\text{'}}}:|{\Psi }_{\mathrm{2}}〉\to |{\Psi }_{\mathrm{3}}〉$

$=\frac{\mathrm{1}}{\sqrt[]{\mathrm{8}}}{\displaystyle \sum _{a=\mathrm{0}}^{\mathrm{7}}} {(-\mathrm{1})}^{{\delta }_{\mathrm{1},a}}{(-\mathrm{1})}^{{\delta }_{\mathrm{1},a^{\mathrm{2}}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{15}}}|a〉|a^{\mathrm{2}}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{15})〉$

$=\frac{\mathrm{1}}{\sqrt[]{\mathrm{8}}}(|\mathrm{0}〉|\mathrm{0}〉+|\mathrm{1}〉|\mathrm{1}〉+|\mathrm{2}〉|\mathrm{4}〉+|\mathrm{3}〉|\mathrm{9}〉$

$-|\mathrm{4}〉|\mathrm{1}〉+|\mathrm{5}〉|\mathrm{10}〉+|\mathrm{6}〉|\mathrm{6}〉+|\mathrm{7}〉|\mathrm{4}〉).$

Step 5-2   Perform the unitary operation $U$ on Reg2, where $U:|a〉|b〉\to |a〉|b\oplus a^{\mathrm{2}}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{15})〉$, obtaining

$U:|{\Psi }_{\mathrm{3}}〉\to |{\Psi }_{\mathrm{4}}〉$

$=\frac{\mathrm{1}}{\sqrt[]{\mathrm{8}}}{\displaystyle \sum _{a=\mathrm{0}}^{\mathrm{7}}} {(-\mathrm{1})}^{{\delta }_{\mathrm{1},a}}{(-\mathrm{1})}^{{\delta }_{\mathrm{1},a^{\mathrm{2}}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{15}}}|a〉|\mathrm{0}〉$

$=\frac{\mathrm{1}}{\sqrt[]{\mathrm{8}}}(|\mathrm{0}〉+|\mathrm{1}〉+|\mathrm{2}〉+|\mathrm{3}〉-|\mathrm{4}〉+|\mathrm{5}〉+|\mathrm{6}〉$

$+|\mathrm{7}〉)|\mathrm{0}〉$

Step 5-3   Perform a Hadamard transform on Reg1.

$H:|{\Psi }_{\mathrm{4}}〉\to |{\Psi }_{\mathrm{5}}〉$

$=H:[\frac{\mathrm{1}}{\sqrt[]{\mathrm{8}}}(|\mathrm{000}〉+|\mathrm{001}〉+|\mathrm{010}〉+|\mathrm{011}〉-|\mathrm{100}〉$

$+|\mathrm{101}〉+|\mathrm{110}〉+|\mathrm{111}〉)]$

$=\frac{\mathrm{1}}{\sqrt[]{\mathrm{8}}}H(|\mathrm{000}〉+|\mathrm{001}〉+|\mathrm{010}〉+|\mathrm{011}〉-|\mathrm{100}〉$

$+|\mathrm{101}〉+|\mathrm{110}〉+|\mathrm{111}〉)$

$\begin{array}{l}=\frac{\mathrm{1}}{\sqrt[]{\mathrm{8}}}\cdot \frac{\mathrm{1}}{\sqrt[]{\mathrm{8}}}[(|\mathrm{0}〉+|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉+|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉+|\mathrm{1}〉)\\ +(|\mathrm{0}〉+|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉+|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉-|\mathrm{1}〉)\\ +(|\mathrm{0}〉+|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉-|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉+|\mathrm{1}〉)\\ +(|\mathrm{0}〉+|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉-|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉-|\mathrm{1}〉)\\ -(|\mathrm{0}〉-|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉+|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉+|\mathrm{1}〉)\\ +(|\mathrm{0}〉-|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉+|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉-|\mathrm{1}〉)\\ +(|\mathrm{0}〉-|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉-|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉+|\mathrm{1}〉)\\ +(|\mathrm{0}〉-|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉-|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉-|\mathrm{1}〉)]\\ =\frac{\mathrm{1}}{\mathrm{4}}(\mathrm{3}|\mathrm{000}〉-|\mathrm{001}〉-|\mathrm{010}〉-|\mathrm{011}〉+|\mathrm{100}〉+|\mathrm{101}〉\\ +|\mathrm{110}〉+|\mathrm{111}〉).\end{array}$

Step 5-4   Perform a conditional phase shift on Reg1 with every computational basis state, except ${|\mathrm{1}〉}^{\otimes \mathrm{3}}$ receiving a phase shift of $-$1 .

$\begin{array}{l}|{\Psi }_{\mathrm{6}}〉=\frac{\mathrm{1}}{\mathrm{4}}(\mathrm{3}|\mathrm{000}〉+|\mathrm{001}〉+|\mathrm{010}〉+|\mathrm{011}〉-|\mathrm{100}〉-\\ |\mathrm{101}〉-|\mathrm{110}〉-|\mathrm{111}〉).\end{array}$

Step 5-5   Perform a Hadamard transform on Reg1.

$\begin{array}{l}H:|{\Psi }_{\mathrm{6}}〉\to |{\Psi }_{\mathrm{7}}〉\\ =H:[\frac{\mathrm{1}}{\mathrm{4}}(\mathrm{3}|\mathrm{000}〉+|\mathrm{001}〉+|\mathrm{010}〉+|\mathrm{011}〉-|\mathrm{100}〉\\ -|\mathrm{101}〉-|\mathrm{110}〉-|\mathrm{111}〉)]\end{array}$

$\begin{array}{l}=\frac{\mathrm{1}}{\mathrm{4}}\cdot \frac{\mathrm{1}}{\sqrt[]{\mathrm{8}}}[\mathrm{3}((|\mathrm{0}〉+|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉+|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉+|\mathrm{1}〉))\\ +(|\mathrm{0}〉+|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉+|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉-|\mathrm{1}〉)\\ +(|\mathrm{0}〉+|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉-|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉+|\mathrm{1}〉)\\ +(|\mathrm{0}〉+|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉-|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉-|\mathrm{1}〉)\\ -(|\mathrm{0}〉-|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉+|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉+|\mathrm{1}〉)\\ -(|\mathrm{0}〉-|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉+|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉-|\mathrm{1}〉)\\ -(|\mathrm{0}〉-|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉-|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉+|\mathrm{1}〉)\end{array}$

$\begin{array}{l}-(|\mathrm{0}〉-|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉-|\mathrm{1}〉)\mathrm{}(|\mathrm{0}〉-|\mathrm{1}〉)]\\ =\frac{\mathrm{1}}{\mathrm{4}\sqrt[]{\mathrm{2}}}(|\mathrm{000}〉+|\mathrm{001}〉+|\mathrm{010}〉+|\mathrm{011}〉+\mathrm{5}|\mathrm{100}〉\end{array}$

$+|\mathrm{101}〉+|\mathrm{110}〉+|\mathrm{111}〉).$

Perform Step 5-1 to Step 5-5 again, we can get

$\begin{array}{l}|\Psi {\text{'}}_{\mathrm{7}}〉=\frac{\mathrm{1}}{\mathrm{8}\sqrt[]{\mathrm{2}}}(-|\mathrm{000}〉-|\mathrm{001}〉-|\mathrm{010}〉-|\mathrm{011}〉+\mathrm{11}|\mathrm{100}〉\\ -|\mathrm{101}〉-|\mathrm{110}〉-|\mathrm{111}〉).\end{array}$

Step 6   Measure Reg1. Suppose that the state $|\mathrm{100}〉$ is observed with a higher probability $\frac{\mathrm{121}}{\mathrm{128}}$, that is, $a=|\mathrm{100}〉=\mathrm{4}$, satisfying $a^{\mathrm{2}}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{15})$.

By Example 1, since the desired $a=\mathrm{4}$ is obtained, we can efficiently compute $\mathrm{g}\mathrm{c}\mathrm{d}(a\pm \mathrm{1},n)=\mathrm{g}\mathrm{c}\mathrm{d}(\mathrm{4}\pm \mathrm{1,15})=(\mathrm{3,5})$ on a classical computer, leading to the prime factorization $\mathrm{15}=\mathrm{3}\times \mathrm{5}$.

In order to more clearly present all of the different algorithms, Table 4 provides a detailed comparison of several algorithms in terms of the success probability, time complexity, and the number of required quantum bits. In Table 4, $\mathrm{3}\varphi (r)/{\mathrm{\pi }}^{\mathrm{2}}r\le P_{\mathrm{S}\mathrm{h}\mathrm{o}\mathrm{r}}<\mathrm{4}\varphi (r)/{\mathrm{\pi }}^{\mathrm{2}}r$, and $\varphi (r)$ is the Euler fuction.

Algorithm 1 inherits the same amplitude amplification property as Grover's search, and its success probability can be made arbitrarily close to 1 after a sufficient number of iterations. Therefore, the success probability of Algorithm 1 is denoted by ≈1 in Table 4.

The idea of Shor's algorithm is surprisingly simple: to factor $n$, one first computes the order $r$ of an element $a$ in the multiplicative group ${\mathit{\mathbb{Z}}}_n^{\mathrm{*}}$ , $\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}(a,n)$. If the computed $r$ is even, then one further computes, with high probability, $\mathrm{g}\mathrm{c}\mathrm{d}\left(a^{r/\mathrm{2}}\pm \mathrm{1},n\right)=\{p,q\}$, with $\mathrm{1}<\{p,q\}<n$. Consequently, if a practical quantum computer capable of efficiently executing Shor's algorithm can be built, the security of RSA would be fundamentally compromised. However, up to now there are no yet quantum computers that could run Shor's algorithm for the large semiprimes $n$ currently used in RSA encryption algorithms. Since the simulation of Grover's algorithm has been demonstrated, we propose an alternative algorithm inspired by Grover's algorithm, which aims to compute $l_a(n)$ using fewer qubits. In fact, based on Grover's algorithm, one can find an integer $r$ satisfying $a^r\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n),$ where the algorithm selects $q^{\text{'}}$ such that $n^{\mathrm{2}}\le q^{\text{'}}={\mathrm{2}}^t$$<\mathrm{2}{n}^{\mathrm{2}}$, with a time complexity of $O\left(\sqrt[]{q^{\text{'}}}\right)$ . That is the algorithm based on Grover's algorithm in Table 4. Whereas in Algorithm 1, we try to find a suitable $a$ such that $a^{\mathrm{2}k}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$ with $k\ge \mathrm{1}$.The most significant advantage of the algorithm lies in its use of fewer quantum bits. This will facilitate the construction of quantum computers using fewer quantum bits, thereby making practical applications more feasible compared with those systems that require more quantum bits.

3 Conclusion

In this paper, through some numerical computations and pieces of evidences of suitable $a$ for which $l_a(n)$ are small and relatively easy to obtain, in the light of quantum integer factorization, we find that the higher the order, the larger the number of $a$. Therefore, from another perspective, it inspires us that, instead of trying to find $l_a(n)$, we should attempt to find a suitable $a$ such that $a^{\mathrm{2}k}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$. Moreover, 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}$ based on Grover's search, but using fewer quantum bits. Moreover, the success probability is close to 1. As this type of $n$ is commonly used as an RSA modulus, once such an $a$ is found, the famous and widely used RSA cryptographic system will be broken completely. As a future direction, one could investigate a quantum algorithm for attacking RSA by exploiting lattice-based shortest vector problems, in conjunction with properties of the Euler totient function and techniques that reduce integer factorization to related computational problems.

References

All Tables

All Figures

	Fig.1 Simplified flowchart of Shor's algorithm
In the text