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

Journal of Tsinghua University(Science and Technology)

Possibility to improve Shor algorithm with grouping algorithm

Liu Li

Published Jan 1, 2008• 0 citations
OpenAlex

Abstract

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.

Related papers

Improving the Success Probability for Shor's Factoring Algorithm

Gregor Leander

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

arXiv:quant-ph/0208183•Aug 29, 2002•10 citations

A precise estimation of the computational complexity in Shor's factoring algorithm

Ken Kuriyama, Seiiti Sano, Shigeru Furuichi

A precise estimation of the computational complexity in Shor's factoring algorithm under the condition that the large integer we want to factorize is composed by the product of two prime numbers, is derived by the results related to number theory. Compared with Shor's original estimation, our estimation shows that one can obtain the solution under such a condition, by less computational complexity.

arXiv:quant-ph/0406145•Jun 21, 2004•4 citations

Distributed Shor's algorithm

Ligang Xiao, Daowen Qiu, Le Luo +1 more

Shor's algorithm is one of the most important quantum algorithm proposed by Peter Shor [Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124--134]. Shor's algorithm can factor a large integer with certain probability and costs polynomial time in the length of the input integer. The key step of Shor's algorithm is the order-finding algorithm, the quantum part of which is to estimate $s/r$, where $r$ is the ``order" and $s$ is some natural number that less than $r$. {{Shor's algorithm requires lots of qubits and a deep circuit depth, which is unaffordable for current physical devices.}} In this paper, to reduce the number of qubits required and circuit depth, we propose a quantum-classical hybrid distributed order-finding algorithm for Shor's algorithm, which combines the advantages of both quantum processing and classical processing. {{ In our distributed order-finding algorithm, we use two quantum computers with the ability of quantum teleportation separately to estimate partial bits of $s/r$.}} The measuring results will be processed through a classical algorithm to ensure the accuracy of the results. Compared with the traditional Shor's algorithm that uses multiple control qubits, our algorithm reduces nearly $L/2$ qubits for factoring an $L$-bit integer and reduces the circuit depth of each computer.

arXiv:2207.05976•Quantum Information and Computation•Jan 1, 2023•39 citations

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

MATHEMATICAL ASPECTS OF SHOR'S ALGORITHM

Christophe Pittet

Abstract. Given a large n-bits integer N < 2n, Shor’s algorithm finds with positive probability a factor of N after O(n2 log n log log n) quantum steps. We describe some of the mathematical aspects of Shor’s algorithm. We mainly follow a description due to M. Batty, S.L. Braunstein, A. J. Duncan and S. Rees. 1.

•Nov 18, 2013•1 citation

A Comparative Analysis of Shor’s Algorithm and Factorization Methods

Alaa Khudhair Abbas, Saba Hussein Rashid, Saba Alaa Abdulwahhab +1 more

Large integer factorization has long been a significant problem in computer science and mathematics. With the advent of Shor's algorithm, a polynomial-time factoring technique created for quantum computers, an effective solution to this problem became possible. Using quantum mechanics concepts. Qantum computing appears to be a novel approach to solving these complex problems. Classical computers are currently using the General Number Field Sieve (GNFS), Trial Division, the Elliptic Curve Method (EC),Fermat's Factorization, and the Quadratic Sieve(QS) are some of the best classical factoring techniques. However, this study examines these conventional approaches to determine their implications for cryptographic security, analyzing their weaknesses, usefulness, strengths, and difficulties. This paper alsodiscusses how Shor's algorithm affects cybersecurity because of its exponential speed advantage over traditional techniques. This paper also uses Shor’s algorithm get Q*P in using quantum facilities to break the algorithm like RSA algorithm

Journal of Al-Nahrain University-Science•Jun 15, 2026•0 citations
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.
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}.
Shor's algorithm is one of the most important quantum algorithm proposed by Peter Shor [Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124--134]. Shor's algorithm can factor a large integer with certain probability and costs polynomial time in the length of the input integer. The key step of Shor's algorithm is the order-finding algorithm, the quantum part of which is to estimate s/rs/rs/r, where rrr is the ``order" and sss is some natural number that less than rrr. {{Shor's algorithm requires lots of qubits and a deep circuit depth, which is unaffordable for current physical devices.}} In this paper, to reduce the number of qubits required and circuit depth, we propose a quantum-classical hybrid distributed order-finding algorithm for Shor's algorithm, which combines the advantages of both quantum processing and classical processing. {{ In our distributed order-finding algorithm, we use two quantum computers with the ability of quantum teleportation separately to estimate partial bits of s/rs/rs/r.}} The measuring results will be processed through a classical algorithm to ensure the accuracy of the results. Compared with the traditional Shor's algorithm that uses multiple control qubits, our algorithm reduces nearly L/2L/2L/2 qubits for factoring an LLL-bit integer and reduces the circuit depth of each computer.
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.
Large integer factorization has long been a significant problem in computer science and mathematics. With the advent of Shor's algorithm, a polynomial-time factoring technique created for quantum computers, an effective solution to this problem became possible. Using quantum mechanics concepts. Qantum computing appears to be a novel approach to solving these complex problems. Classical computers are currently using the General Number Field Sieve (GNFS), Trial Division, the Elliptic Curve Method (EC),Fermat's Factorization, and the Quadratic Sieve(QS) are some of the best classical factoring techniques. However, this study examines these conventional approaches to determine their implications for cryptographic security, analyzing their weaknesses, usefulness, strengths, and difficulties. This paper alsodiscusses how Shor's algorithm affects cybersecurity because of its exponential speed advantage over traditional techniques. This paper also uses Shor’s algorithm get Q*P in using quantum facilities to break the algorithm like RSA algorithm