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

International Symposium on Information Science and Engineering

On the Complexity of Shor's Algorithm for Factorization

Zhengjun Cao, Lihua Liu

Published Dec 1, 2009• 8 citations
Publisher

Abstract

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.

DOI
10.1109/isise.2009.86

Related papers

Shor's factorization algorithm

E. Desurvire

This chapter describes what is generally considered to be one of the most important and historical contributions to the field of quantum computing, namely Shor's factorization algorithm . As its name indicates, this algorithm makes it possible to factorize numbers, which consists in their decomposition into a unique product of prime numbers. Other classical factorization algorithms previously developed have a complexity or computing time that increases exponentially with the number size, making the task intractable if not hopeless for large numbers. In contrast, Shor's algorithm is able to factor a number of any size in polynomial time , making the factorization problem tractable should a quantum computer ever be realized in the future. Since Shor's algorithm is based on several nonintuitive properties and other mathematical subtleties, this chapter presents a certain level of difficulty. With the previous chapters and tools readily assimilated, and some patience in going through the different preliminary steps required, such a difficulty is, however, quite surmountable. I have sought to make this description of Shor's algorithm as mathematically complete as possible and crack-free, while avoiding some academic considerations that may not be deemed necessary from any engineering perspective. Eventually, Shor's algorithm is described in only a few basic instructions. What is conceptually challenging is to grasp why it works so well, and also to feel comfortable with the fact that its implementation actually takes a fair amount of trial and error. The two preliminaries of Shor's algorithm are the phase estimation and the related order-finding algorithms.

Cambridge University Press eBooks•Feb 19, 2009•0 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

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

Analysis of RSA and Shor’s algorithm for cryptography: A quantum perspective

Seema Kute, Chitra G. Desai, Mukti E. Jadhav

The complexity of public key algorithms like RSA and variants of Elgamal is based on the involvement of exponentiation in encryption and decryption. RSA is based on integer factorization and variants of Elgamal or based on discrete logarithms and are formed as hard problems. To achieve the perceived level of security, the required key length for public key cryptosystem needs to be determined. Quantum computers are capable of conducting an exponential number of simultaneous computations because of which they can find factors in polynomial time. Shor’s algorithm is popular algorithm for factoring huge integers in polynomial time on quantum computers. This paper presents RSA algorithm followed by various possible attacks for factoring and demonstrates Shor’s algorithm for factoring and discuss results for interpretations.

AIP conference proceedings•Jan 1, 2024•5 citations

On Shor's Factoring Algorithm with More Registers and the Problem to Certify Quantum Computers

Zhengjun Cao, Zhenfu Cao

Shor's factoring algorithm uses two quantum registers. By introducing more registers we show that the measured numbers in these registers which are of the same pre-measurement state, should be equal if the original Shor's complexity argument is sound. This contradicts the argument that the second register has $r$ possible measured values. There is an anonymous comment which argues that the states in these registers are entangled. If so, the entanglement involving many quantum registers can not be interpreted by the mechanism of EPR pairs and the like. In view of this peculiar entanglement has not yet been mentioned and investigated, we think the claim that the Shor's algorithm runs in polynomial time needs more physical verifications. We also discuss the problem to certify quantum computers.

arXiv:1409.7352•Sep 10, 2014•5 citations

On the Various Ways of Quantum Implementation of the Modular Exponentiation Function for Shor’s Factorization

Jiří Tomčala

Abstract The content of this paper is a detailed analysis of possible ways how to quantum implement a key part of Shor’s factorization algorithm, the modular exponentiation function. This implementation is a bottleneck for performing quantum factorization with polynomial complexity, which would make it possible to factorize really large numbers in a reasonable amount of time. In this paper, not only the general theory is presented, but also the results of successful factorizations of the numbers 247 and 143 using Shor’s algorithm from a quantum computer simulator. An interesting fact is that no ancillary qubits were needed in these factorizations. Based on the content of the paper, the conclusion also suggests possible future work on the development of this modular exponentiation function implementation.

International Journal of Theoretical Physics•Jan 10, 2024•7 citations
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.
This chapter describes what is generally considered to be one of the most important and historical contributions to the field of quantum computing, namely Shor's factorization algorithm . As its name indicates, this algorithm makes it possible to factorize numbers, which consists in their decomposition into a unique product of prime numbers. Other classical factorization algorithms previously developed have a complexity or computing time that increases exponentially with the number size, making the task intractable if not hopeless for large numbers. In contrast, Shor's algorithm is able to factor a number of any size in polynomial time , making the factorization problem tractable should a quantum computer ever be realized in the future. Since Shor's algorithm is based on several nonintuitive properties and other mathematical subtleties, this chapter presents a certain level of difficulty. With the previous chapters and tools readily assimilated, and some patience in going through the different preliminary steps required, such a difficulty is, however, quite surmountable. I have sought to make this description of Shor's algorithm as mathematically complete as possible and crack-free, while avoiding some academic considerations that may not be deemed necessary from any engineering perspective. Eventually, Shor's algorithm is described in only a few basic instructions. What is conceptually challenging is to grasp why it works so well, and also to feel comfortable with the fact that its implementation actually takes a fair amount of trial and error. The two preliminaries of Shor's algorithm are the phase estimation and the related order-finding algorithms.
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
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 complexity of public key algorithms like RSA and variants of Elgamal is based on the involvement of exponentiation in encryption and decryption. RSA is based on integer factorization and variants of Elgamal or based on discrete logarithms and are formed as hard problems. To achieve the perceived level of security, the required key length for public key cryptosystem needs to be determined. Quantum computers are capable of conducting an exponential number of simultaneous computations because of which they can find factors in polynomial time. Shor’s algorithm is popular algorithm for factoring huge integers in polynomial time on quantum computers. This paper presents RSA algorithm followed by various possible attacks for factoring and demonstrates Shor’s algorithm for factoring and discuss results for interpretations.
Shor's factoring algorithm uses two quantum registers. By introducing more registers we show that the measured numbers in these registers which are of the same pre-measurement state, should be equal if the original Shor's complexity argument is sound. This contradicts the argument that the second register has rrr possible measured values. There is an anonymous comment which argues that the states in these registers are entangled. If so, the entanglement involving many quantum registers can not be interpreted by the mechanism of EPR pairs and the like. In view of this peculiar entanglement has not yet been mentioned and investigated, we think the claim that the Shor's algorithm runs in polynomial time needs more physical verifications. We also discuss the problem to certify quantum computers.
Abstract The content of this paper is a detailed analysis of possible ways how to quantum implement a key part of Shor’s factorization algorithm, the modular exponentiation function. This implementation is a bottleneck for performing quantum factorization with polynomial complexity, which would make it possible to factorize really large numbers in a reasonable amount of time. In this paper, not only the general theory is presented, but also the results of successful factorizations of the numbers 247 and 143 using Shor’s algorithm from a quantum computer simulator. An interesting fact is that no ancillary qubits were needed in these factorizations. Based on the content of the paper, the conclusion also suggests possible future work on the development of this modular exponentiation function implementation.