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

arXiv:2406.04061

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

Luis Victor Dieulefait, Jorge Jiménez Urroz

Published Jun 6, 2024• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2406.04061

Related papers

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•2 citations

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

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

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 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

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

Peng LI, Yue Wang, Xinxia WANG +1 more

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.

Wuhan University Journal of Natural Sciences•Jun 1, 2026•0 citations
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.
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.
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].
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.
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.