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:quant-ph/0208183

Improving the Success Probability for Shor's Factoring Algorithm

Gregor Leander

Published Aug 29, 2002• 10 citations
arXivHTMLPDF

Abstract

Given n=p*q with p and q prim and y in Z_{p*q}^*. Shor's Algorithm computes the order r of y, i.e. y^r=1 (mod n). If r=2k is even and y^k \ne -1 (mod n) we can easily compute a non trivial factor of n: gcd(y^k-1,n). In the original paper it is shown that a randomly chosen y is usable for factoring with probabily {1/2}. In this paper we will show an efficient possibility to improve the lower bound of this probability by selecting only special y in Z_n^* to {3/4}, so we are able to reduce the fault probabilty in the worst case from {1/2} to {1/4}.

DOI
10.48550/arxiv.quant-ph/0208183

Related papers

How to detect whether Shor’s algorithm succeeds against large integers without a quantum computer

Daniel Chicayban Bastos, Luis Antônio Brasil Kowada

Shor’s algorithm is a well-known probabilistic method for factoring large composite integers in polynomial-time on a quantum computer. The method computes the order r of a random element x in the group Z∗N and uses that information for splitting N with an application of the greatest common divisor algorithm. However, being probabilistic, the success of Shor’s algorithm relies on some special properties of N. If r is even and xr/2 £ -1 mod N, then gcd(xr/2 - 1, N) reveals a nontrivial factor of N and the method succeeds. But even assuming that r is even and being given the complete prime factorization of N it is not obvious whether xr/2 £ -1 mod N and, therefore, it is not easy to assert whether Shor’s algorithm would split N without running it and looking at its answer. We present a strategy for detecting whether the splitting occurs without any need for running the quantum order-finding algorithm, but we must be given the prime factorization of N. This has allowed us to produce the first direct evidence of the probability of success of Shor’s method. The composites chosen were the product of two randomly-generated probable primes of similar sizes that pass the Miller-Rabin test.

Procedia Computer Science•Jan 1, 2021•9 citations

Possibility to improve Shor algorithm with grouping algorithm

Liu Li

The grouping algorithm might be used to reduce the complexity of the traditional Shor algorithm to linear complexity,and to enhance the calculate capacity of duality computers.This paper analyzes this possibility mostly based on mathematical theoretical analysis,applying number theory and probability theory.The work discusses mainly two cases:1) bases randomly selected(in accordance to the original idea of Shor);2) some chosen with higher probabilities.In the second case,certain N is proved not to satisfy the linear restriction for any arbitrary k,and the distribution of such N among positive integers is also discussed.In conclusion,the grouping method is not effective in both cases.The Shor algorithm is still the optimal method for factoring large numbers.

Journal of Tsinghua University(Science and Technology)•Jan 1, 2008•0 citations

On the Complexity of Shor's Algorithm for Factorization

Zhengjun Cao, Lihua Liu

The complexity analysis of Shor's quantum algorithm for factorization consists of: 1) The probability p that we see any particular state\c, xk(mod n)) with {rc}q¿ r/2 is at least 1/3r2. 2) There are ¿(r) possible values of c, and r possible values of xk(mod n). 3) The success probability is at least ¿(r) · r · 1/3r2. That is, the inventor views p as the joint probability P(X = c, Y = xk(mod n)). In this paper, we show that the argument for the estimation of P(X = c, Y = xk(mod n)) is not sound. Therefore, the problem that Shor's algorithm takes polynomial time remains open.

International Symposium on Information Science and Engineering•Dec 1, 2009•8 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

On completely factoring any integer efficiently in a single run of an order-finding algorithm

Martin Ekerå

Abstract We show that given the order of a single element selected uniformly at random from $${\mathbb {Z}}_N^*$$ Z N ∗ , we can with very high probability, and for any integer N, efficiently find the complete factorization of N in polynomial time. This implies that a single run of the quantum part of Shor’s factoring algorithm is usually sufficient. All prime factors of N can then be recovered with negligible computational cost in a classical post-processing step. The classical algorithm required for this step is essentially due to Miller.

arXiv:2007.10044•Quantum Information Processing•Jun 1, 2021•15 citations

Large-Scale Simulation of Shor’s Quantum Factoring Algorithm

Dennis Willsch, Madita Willsch, Fengping Jin +2 more

Shor’s factoring algorithm is one of the most anticipated applications of quantum computing. However, the limited capabilities of today’s quantum computers only permit a study of Shor’s algorithm for very small numbers. Here, we show how large GPU-based supercomputers can be used to assess the performance of Shor’s algorithm for numbers that are out of reach for current and near-term quantum hardware. First, we study Shor’s original factoring algorithm. While theoretical bounds suggest success probabilities of only 3–4%, we find average success probabilities above 50%, due to a high frequency of “lucky” cases, defined as successful factorizations despite unmet sufficient conditions. Second, we investigate a powerful post-processing procedure, by which the success probability can be brought arbitrarily close to one, with only a single run of Shor’s quantum algorithm. Finally, we study the effectiveness of this post-processing procedure in the presence of typical errors in quantum processing hardware. We find that the quantum factoring algorithm exhibits a particular form of universality and resilience against the different types of errors. The largest semiprime that we have factored by executing Shor’s algorithm on a GPU-based supercomputer, without exploiting prior knowledge of the solution, is 549,755,813,701 = 712,321 × 771,781. We put forward the challenge of factoring, without oversimplification, a non-trivial semiprime larger than this number on any quantum computing device.

arXiv:2308.05047•Mathematics•Oct 9, 2023•41 citations
Given n=pq with p and q prim and y in Z_{pq}^. Shor's Algorithm computes the order r of y, i.e. y^r=1 (mod n). If r=2k is even and y^k \ne -1 (mod n) we can easily compute a non trivial factor of n: gcd(y^k-1,n). In the original paper it is shown that a randomly chosen y is usable for factoring with probabily {1/2}. In this paper we will show an efficient possibility to improve the lower bound of this probability by selecting only special y in Z_n^ to {3/4}, so we are able to reduce the fault probabilty in the worst case from {1/2} to {1/4}.
Shor’s algorithm is a well-known probabilistic method for factoring large composite integers in polynomial-time on a quantum computer. The method computes the order r of a random element x in the group Z∗N and uses that information for splitting N with an application of the greatest common divisor algorithm. However, being probabilistic, the success of Shor’s algorithm relies on some special properties of N. If r is even and xr/2 £ -1 mod N, then gcd(xr/2 - 1, N) reveals a nontrivial factor of N and the method succeeds. But even assuming that r is even and being given the complete prime factorization of N it is not obvious whether xr/2 £ -1 mod N and, therefore, it is not easy to assert whether Shor’s algorithm would split N without running it and looking at its answer. We present a strategy for detecting whether the splitting occurs without any need for running the quantum order-finding algorithm, but we must be given the prime factorization of N. This has allowed us to produce the first direct evidence of the probability of success of Shor’s method. The composites chosen were the product of two randomly-generated probable primes of similar sizes that pass the Miller-Rabin test.
The grouping algorithm might be used to reduce the complexity of the traditional Shor algorithm to linear complexity,and to enhance the calculate capacity of duality computers.This paper analyzes this possibility mostly based on mathematical theoretical analysis,applying number theory and probability theory.The work discusses mainly two cases:1) bases randomly selected(in accordance to the original idea of Shor);2) some chosen with higher probabilities.In the second case,certain N is proved not to satisfy the linear restriction for any arbitrary k,and the distribution of such N among positive integers is also discussed.In conclusion,the grouping method is not effective in both cases.The Shor algorithm is still the optimal method for factoring large numbers.
The complexity analysis of Shor's quantum algorithm for factorization consists of: 1) The probability p that we see any particular state\c, xk(mod n)) with {rc}q¿ r/2 is at least 1/3r2. 2) There are ¿(r) possible values of c, and r possible values of xk(mod n). 3) The success probability is at least ¿(r) · r · 1/3r2. That is, the inventor views p as the joint probability P(X = c, Y = xk(mod n)). In this paper, we show that the argument for the estimation of P(X = c, Y = xk(mod n)) is not sound. Therefore, the problem that Shor's algorithm takes polynomial time remains open.
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
Abstract We show that given the order of a single element selected uniformly at random from ZN∗{\mathbb {Z}}_N^*ZN∗​ Z N ∗ , we can with very high probability, and for any integer N, efficiently find the complete factorization of N in polynomial time. This implies that a single run of the quantum part of Shor’s factoring algorithm is usually sufficient. All prime factors of N can then be recovered with negligible computational cost in a classical post-processing step. The classical algorithm required for this step is essentially due to Miller.
Shor’s factoring algorithm is one of the most anticipated applications of quantum computing. However, the limited capabilities of today’s quantum computers only permit a study of Shor’s algorithm for very small numbers. Here, we show how large GPU-based supercomputers can be used to assess the performance of Shor’s algorithm for numbers that are out of reach for current and near-term quantum hardware. First, we study Shor’s original factoring algorithm. While theoretical bounds suggest success probabilities of only 3–4%, we find average success probabilities above 50%, due to a high frequency of “lucky” cases, defined as successful factorizations despite unmet sufficient conditions. Second, we investigate a powerful post-processing procedure, by which the success probability can be brought arbitrarily close to one, with only a single run of Shor’s quantum algorithm. Finally, we study the effectiveness of this post-processing procedure in the presence of typical errors in quantum processing hardware. We find that the quantum factoring algorithm exhibits a particular form of universality and resilience against the different types of errors. The largest semiprime that we have factored by executing Shor’s algorithm on a GPU-based supercomputer, without exploiting prior knowledge of the solution, is 549,755,813,701 = 712,321 × 771,781. We put forward the challenge of factoring, without oversimplification, a non-trivial semiprime larger than this number on any quantum computing device.