Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Wuhan University Journal of Natural Sciences

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

Peng LI, Yue Wang, Xinxia WANG, Huanguo Zhang

Published Jun 1, 2026• 0 citations
Publisher

Abstract

The order [see formula in PDF] of an element [see formula in PDF] in the multiplicative group [see formula in PDF], denoted by [see formula in PDF], or [see formula in PDF] 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 [see formula in PDF] for which [see formula in PDF] 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 [see formula in PDF]. Therefore, we propose a quantum algorithm for finding [see formula in PDF] in [see formula in PDF] with [see formula in PDF], explicitly excluding the trivial solution [see formula in PDF], 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 [see formula in PDF] is commonly used as an RSA modulus, once such an [see formula in PDF] is found, RSA cryptographic system will be broken.

DOI
10.1051/wujns/2026313241

Related papers

On factoring integers, and computing discrete logarithms and orders, quantumly

Martin Ekerå

This thesis contains a collection of efficient quantum algorithms and classical pre- and post-processing algorithms for various number- and group-theoretical problems with concrete cryptanalytical applications. More specifically, the focus is on the integer factoring problem (IFP), the discrete logarithm problem (DLP), and the order-finding problem (OFP), and on certain important variations of these problems. It is for example explained how the OFP and complete IFP may be solved efficiently in a single run of a reduced version of Shor's algorithm for the OFP with very high success probability, as evidenced by a lower bound that is 1 − o(1), how the short DLP in groups of unknown order may be solved efficiently and with an advantage over Shor's algorithm for the DLP (that furthermore requires the order to be known), as evidenced by a lower bound on the single-run success probability that is 1 − o(1), how the RSA IFP may be solved efficiently and with an advantage over Shor's algorithm for the IFP, by reducing the RSA IFP to a short DLP, how the DLP may heuristically be solved efficiently, and with high success probability that is 1 − o(1), in a single run of a reduced version of Shor’s algorithm for the DLP that admits efficient implementation, how the DLP may be solved in groups of unknown order, such as Schnorr groups, by jointly solving an OFP and a DLP at lower overall cost but higher per-run cost compared to first solving the OFP and then the DLP, how tradeoffs — between the number of group operations that are evaluated quantumly and the number of runs that are required — may be achieved in all of the aforementioned algorithms, and how all of the aforementioned algorithms may be simulated efficiently classically, for arbitrary large cryptographically relevant problem instances, when the solution to the instance is known, enabling the number of runs required when performing tradeoffs to be tightly estimated. It is furthermore for example explained how Regev's recent quantum algorithm for the IFP may be extended to the DLP and OFP, yielding i) a reduction in the circuit size and depth by a factor compared to Shor for these problems when working in , for N an n-bit integer, at the expense of performing runs, and ii) slight improvements of Regev's orginal algorithm for the IFP, how the above algorithms may be simulated efficiently classically, for large special-form problem instances that are classically tractable, and that Regev’s post-processing, and the post-processing for our extensions, are robust to an arbitrarily large fraction < 1 of the runs being bad. The above has implications for cryptography based on the intractability of the IFP and DLP — including but not limited to for widely used schemes such as RSA, DSA and Diffie–Hellman. The algorithms in this thesis are all derived from, and make notable improvements to, the seminal works of Shor. Some of the contributions are joint works with other authors.

•Jan 1, 2024•0 citations

A new quantum algorithm for computing RSA ciphertext period

Yahui Wang, Songyuan Yan, Huanguo Zhang

Shor proposed a quantum polynomial-time integer factorization algorithm to break the RSA public-key cryptosystem. In this paper, we propose a new quantum algorithm for breaking RSA by computing the order of the RSA ciphertext C . The new algorithm has the following properties: 1) recovering the RSA plaintext M from the ciphertext C without factoring n ; 2) avoiding the even order of the element; 3) having higher success probability than Shor’s; 4) having the same complexity as Shor’s.

Wuhan University Journal of Natural Sciences•Jan 9, 2017•5 citations

Quantum Algorithm for Attacking RSA Based on Fourier Transform and Fixed-Point

Yahui Wang, Huanguo ZHANG

Shor in 1994 proposed a quantum polynomial-time algorithm for finding the order r of an element a in the multiplicative group Zn*, which can be used to factor the integer n by computing [see formula in PDF] and hence break the famous RSA cryptosystem. However, the order r must be even. This restriction can be removed. So in this paper, we propose a quantum polynomial-time fixed-point attack for directly recovering the RSA plaintext M from the ciphertext C, without explicitly factoring the modulus n. Compared to Shor’s algorithm, the order r of the fixed-point C for RSA(e, n) satisfying [see formula in PDF] does not need to be even. Moreover, the success probability of the new algorithm is at least [see formula in PDF] and higher than that of Shor’s algorithm, though the time complexity for both algorithms is about the same.

Wuhan University Journal of Natural Sciences•Dec 1, 2021•4 citations

A Note on Shor's Quantum Algorithm for Prime Factorization.

Zhengjun Cao

Abstract It’s well known that Shor[1] proposed a polynomial time algorithm for prime factorization by using quantum computers. For a given number n, he gave an algorithm for finding the order r of an element x (mod n) instead of giving an algorithm for factoring n directly. The indirect algorithm is feasible because factor-ization can be reduced to finding the order of an element by using randomization[2]. But a point should be stressed that the order of the number must be even. Actually, the restriction can be removed in a particular case. In this paper, we show that factoring RSA modulus (a product of two primes) only needs to find the order of 2, whether it is even or not. Keywords Shor’s quantum algorithm, RSA modulus. 1

•Jan 1, 2005•1 citation

Computing $φ(N)$ for an RSA module with a single quantum query

Luis Victor Dieulefait, Jorge Jiménez Urroz

In this paper we give a polynomial time algorithm to compute $φ(N)$ for an RSA module $N$ using as input the order modulo $N$ of a randomly chosen integer. This provides a new insight in the very important problem of factoring an RSA module with extra information. In fact, the algorithm is extremely simple and consists only on a computation of a greatest common divisor, two multiplications and a division. The algorithm works with a probability of at least $1-\frac{1}{N^{1/2-ε}}$, where $ε$ is any small positive constant.

arXiv:2406.04061•Jun 6, 2024•0 citations

Computing $$\varphi (N)$$ for an RSA module with a single quantum query

Luis Victor Dieulefait, Jorge Jiménez Urroz

Abstract In this paper, we give a polynomial time algorithm to compute $$\varphi (N)$$ φ ( N ) for an RSA module N using as input the order modulo N of a randomly chosen integer. This provides a new insight in the very important problem of factoring an RSA module with extra information. In fact, the algorithm is extremely simple and consists only on a computation of a greatest common divisor, two multiplications and a division. The algorithm works with a probability of at least $$1-\frac{1}{N^{1/2-\epsilon }}$$ 1 - 1 N 1 / 2 - ϵ , where $$\epsilon $$ ϵ is any small positive constant.

Quantum Information Processing•Nov 27, 2025•3 citations
The order [see formula in PDF] of an element [see formula in PDF] in the multiplicative group [see formula in PDF], denoted by [see formula in PDF], or [see formula in PDF] 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 [see formula in PDF] for which [see formula in PDF] 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 [see formula in PDF]. Therefore, we propose a quantum algorithm for finding [see formula in PDF] in [see formula in PDF] with [see formula in PDF], explicitly excluding the trivial solution [see formula in PDF], 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 [see formula in PDF] is commonly used as an RSA modulus, once such an [see formula in PDF] is found, RSA cryptographic system will be broken.
This thesis contains a collection of efficient quantum algorithms and classical pre- and post-processing algorithms for various number- and group-theoretical problems with concrete cryptanalytical applications. More specifically, the focus is on the integer factoring problem (IFP), the discrete logarithm problem (DLP), and the order-finding problem (OFP), and on certain important variations of these problems. It is for example explained how the OFP and complete IFP may be solved efficiently in a single run of a reduced version of Shor's algorithm for the OFP with very high success probability, as evidenced by a lower bound that is 1 − o(1), how the short DLP in groups of unknown order may be solved efficiently and with an advantage over Shor's algorithm for the DLP (that furthermore requires the order to be known), as evidenced by a lower bound on the single-run success probability that is 1 − o(1), how the RSA IFP may be solved efficiently and with an advantage over Shor's algorithm for the IFP, by reducing the RSA IFP to a short DLP, how the DLP may heuristically be solved efficiently, and with high success probability that is 1 − o(1), in a single run of a reduced version of Shor’s algorithm for the DLP that admits efficient implementation, how the DLP may be solved in groups of unknown order, such as Schnorr groups, by jointly solving an OFP and a DLP at lower overall cost but higher per-run cost compared to first solving the OFP and then the DLP, how tradeoffs — between the number of group operations that are evaluated quantumly and the number of runs that are required — may be achieved in all of the aforementioned algorithms, and how all of the aforementioned algorithms may be simulated efficiently classically, for arbitrary large cryptographically relevant problem instances, when the solution to the instance is known, enabling the number of runs required when performing tradeoffs to be tightly estimated. It is furthermore for example explained how Regev's recent quantum algorithm for the IFP may be extended to the DLP and OFP, yielding i) a reduction in the circuit size and depth by a factor compared to Shor for these problems when working in , for N an n-bit integer, at the expense of performing runs, and ii) slight improvements of Regev's orginal algorithm for the IFP, how the above algorithms may be simulated efficiently classically, for large special-form problem instances that are classically tractable, and that Regev’s post-processing, and the post-processing for our extensions, are robust to an arbitrarily large fraction < 1 of the runs being bad. The above has implications for cryptography based on the intractability of the IFP and DLP — including but not limited to for widely used schemes such as RSA, DSA and Diffie–Hellman. The algorithms in this thesis are all derived from, and make notable improvements to, the seminal works of Shor. Some of the contributions are joint works with other authors.
Shor in 1994 proposed a quantum polynomial-time algorithm for finding the order r of an element a in the multiplicative group Zn*, which can be used to factor the integer n by computing [see formula in PDF] and hence break the famous RSA cryptosystem. However, the order r must be even. This restriction can be removed. So in this paper, we propose a quantum polynomial-time fixed-point attack for directly recovering the RSA plaintext M from the ciphertext C, without explicitly factoring the modulus n. Compared to Shor’s algorithm, the order r of the fixed-point C for RSA(e, n) satisfying [see formula in PDF] does not need to be even. Moreover, the success probability of the new algorithm is at least [see formula in PDF] and higher than that of Shor’s algorithm, though the time complexity for both algorithms is about the same.
Abstract It’s well known that Shor[1] proposed a polynomial time algorithm for prime factorization by using quantum computers. For a given number n, he gave an algorithm for finding the order r of an element x (mod n) instead of giving an algorithm for factoring n directly. The indirect algorithm is feasible because factor-ization can be reduced to finding the order of an element by using randomization[2]. But a point should be stressed that the order of the number must be even. Actually, the restriction can be removed in a particular case. In this paper, we show that factoring RSA modulus (a product of two primes) only needs to find the order of 2, whether it is even or not. Keywords Shor’s quantum algorithm, RSA modulus. 1
Computing φ(N)φ(N)φ(N) for an RSA module with a single quantum query
In this paper we give a polynomial time algorithm to compute φ(N)φ(N)φ(N) for an RSA module NNN using as input the order modulo NNN of a randomly chosen integer. This provides a new insight in the very important problem of factoring an RSA module with extra information. In fact, the algorithm is extremely simple and consists only on a computation of a greatest common divisor, two multiplications and a division. The algorithm works with a probability of at least 1−1N1/2−ε1-\frac{1}{N^{1/2-ε}}1−N1/2−ε1​, where εεε is any small positive constant.
Computing φ(N)\varphi (N)φ(N) for an RSA module with a single quantum query
Abstract In this paper, we give a polynomial time algorithm to compute φ(N)\varphi (N)φ(N) φ ( N ) for an RSA module N using as input the order modulo N of a randomly chosen integer. This provides a new insight in the very important problem of factoring an RSA module with extra information. In fact, the algorithm is extremely simple and consists only on a computation of a greatest common divisor, two multiplications and a division. The algorithm works with a probability of at least 1−1N1/2−ϵ1-\frac{1}{N^{1/2-\epsilon }}1−N1/2−ϵ1​ 1 - 1 N 1 / 2 - ϵ , where ϵ\epsilon ϵ ϵ is any small positive constant.