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

Quantum Information Processing

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

Luis Victor Dieulefait, Jorge Jiménez Urroz

Published Nov 27, 2025• 2 citations
Publisher

Abstract

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.

DOI
10.1007/s11128-025-05008-w

Related papers

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

Exact quantum query complexity of computing Hamming weight modulo powers of two and three

Arjan Cornelissen, Nikhil S. Mande, Māris Ozols +1 more

We study the problem of computing the Hamming weight of an $n$-bit string modulo $m$, for any positive integer $m \leq n$ whose only prime factors are 2 and 3. We show that the exact quantum query complexity of this problem is $\left\lceil n(1 - 1/m) \right\rceil$. The upper bound is via an iterative query algorithm whose core components are the well-known 1-query quantum algorithm (essentially due to Deutsch) to compute the Hamming weight a 2-bit string mod 2 (i.e., the parity of the input bits), and a new 2-query quantum algorithm to compute the Hamming weight of a 3-bit string mod 3. We show a matching lower bound (in fact for arbitrary moduli $m$) via a variant of the polynomial method [de Wolf, SIAM J. Comput., 32(3), 2003]. This bound is for the weaker task of deciding whether or not a given $n$-bit input has Hamming weight 0 modulo $m$, and it holds even in the stronger non-deterministic quantum query model where an algorithm must have positive acceptance probability iff its input evaluates to 1. For $m>2$ our lower bound exceeds $n/2$, beating the best lower bound provable using the general polynomial method [Theorem 4.3, Beals et al., J. ACM 48(4), 2001].

arXiv:2112.14682•Dec 29, 2021•1 citation

On Computing

The order r of an element a in the multiplicative group (Z/nZ)*, denoted by order (a,n), or la(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 la(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 a2k≡1 (mod n) with k≥1, explicitly excluding the trivial solution a≡1 (mod 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.

•Jun 24, 2026•0 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 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•4 citations

Quantum polynomial-time fixed-point attack for RSA

Yahui Wang, Huanguo Zhang, Houzhen Wang

Security analysis of public-key cryptosystems is of fundamental significance for both theoretical research and applications in cryptography. In particular, the security of widely used public-key cryptosystems merits deep research to protect against new types of attacks. It is therefore highly meaningful to research cryptanalysis in the quantum computing environment. Shor proposed a well-known factoring algorithm by finding the prime factors of a number n = pq, which is exponentially faster than the best known classical algorithm. The idea behind Shor's quantum factoring algorithm is a straightforward programming consequence of the following proposition: to factor n, it suffices to find the order r; once such an r is found, one can compute gcd(ar/2± 1, n) = p or q. For odd values of r it is assumed that the factors of n cannot be found (since ar/2is not generally an integer). That is, the order r must be even. This restriction can be removed, however, by working from another angle. Based on the quantum inverse Fourier transform and phase estimation, this paper presents a new polynomial-time quantum algorithm for breaking RSA, without explicitly factoring the modulus n. The probability of success of the new algorithm is greater than 4φ(r)/π2r, exceeding that of the existing quantum algorithm for attacking RSA based on factorization. In constrast to the existing quantum algorithm for attacking RSA, the order r of the fixed point C for RSA does not need to be even. It changed the practices that cryptanalysts try to recover the private-key, directly from recovering the plaintext M to start, a ciphertext-only attack attacking RSA is proposed.

China Communications•Feb 1, 2018•33 citations
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.
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.
We study the problem of computing the Hamming weight of an nnn-bit string modulo mmm, for any positive integer m≤nm \leq nm≤n whose only prime factors are 2 and 3. We show that the exact quantum query complexity of this problem is ⌈n(1−1/m)⌉\left\lceil n(1 - 1/m) \right\rceil⌈n(1−1/m)⌉. The upper bound is via an iterative query algorithm whose core components are the well-known 1-query quantum algorithm (essentially due to Deutsch) to compute the Hamming weight a 2-bit string mod 2 (i.e., the parity of the input bits), and a new 2-query quantum algorithm to compute the Hamming weight of a 3-bit string mod 3. We show a matching lower bound (in fact for arbitrary moduli mmm) via a variant of the polynomial method [de Wolf, SIAM J. Comput., 32(3), 2003]. This bound is for the weaker task of deciding whether or not a given nnn-bit input has Hamming weight 0 modulo mmm, and it holds even in the stronger non-deterministic quantum query model where an algorithm must have positive acceptance probability iff its input evaluates to 1. For m>2m>2m>2 our lower bound exceeds n/2n/2n/2, beating the best lower bound provable using the general polynomial method [Theorem 4.3, Beals et al., J. ACM 48(4), 2001].
The order r of an element a in the multiplicative group (Z/nZ)*, denoted by order (a,n), or la(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 la(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 a2k≡1 (mod n) with k≥1, explicitly excluding the trivial solution a≡1 (mod 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.
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.
Security analysis of public-key cryptosystems is of fundamental significance for both theoretical research and applications in cryptography. In particular, the security of widely used public-key cryptosystems merits deep research to protect against new types of attacks. It is therefore highly meaningful to research cryptanalysis in the quantum computing environment. Shor proposed a well-known factoring algorithm by finding the prime factors of a number n = pq, which is exponentially faster than the best known classical algorithm. The idea behind Shor's quantum factoring algorithm is a straightforward programming consequence of the following proposition: to factor n, it suffices to find the order r; once such an r is found, one can compute gcd(ar/2± 1, n) = p or q. For odd values of r it is assumed that the factors of n cannot be found (since ar/2is not generally an integer). That is, the order r must be even. This restriction can be removed, however, by working from another angle. Based on the quantum inverse Fourier transform and phase estimation, this paper presents a new polynomial-time quantum algorithm for breaking RSA, without explicitly factoring the modulus n. The probability of success of the new algorithm is greater than 4φ(r)/π2r, exceeding that of the existing quantum algorithm for attacking RSA based on factorization. In constrast to the existing quantum algorithm for attacking RSA, the order r of the fixed point C for RSA does not need to be even. It changed the practices that cryptanalysts try to recover the private-key, directly from recovering the plaintext M to start, a ciphertext-only attack attacking RSA is proposed.