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

Factoring Safe Semiprimes with a Single Quantum Query

Frédéric Grosshans, Thomas Lawson, François Morain, Benjamin Smith

Published Nov 13, 2015• 15 citations
arXivHTMLPDF

Abstract

Shor's factoring algorithm (SFA), by its ability to efficiently factor large numbers, has the potential to undermine contemporary encryption. At its heart is a process called order finding, which quantum mechanics lets us perform efficiently. SFA thus consists of a \emph{quantum order finding algorithm} (QOFA), bookended by classical routines which, given the order, return the factors. But, with probability up to $1/2$, these classical routines fail, and QOFA must be rerun. We modify these routines using elementary results in number theory, improving the likelihood that they return the factors. The resulting quantum factoring algorithm is better than SFA at factoring safe semiprimes, an important class of numbers used in cryptography. With just one call to QOFA, our algorithm almost always factors safe semiprimes. As well as a speed-up, improving efficiency gives our algorithm other, practical advantages: unlike SFA, it does not need a randomly picked input, making it simpler to construct in the lab; and in the (unlikely) case of failure, the same circuit can be rerun, without modification. We consider generalizing this result to other cases, although we do not find a simple extension, and conclude that SFA is still the best algorithm for general numbers (non safe semiprimes, in other words). Even so, we present some simple number theoretic tricks for improving SFA in this case.

DOI
10.48550/arxiv.1511.04385

Related papers

Simulating Shor's Algorithm with QuantumRings and the Emerging Threats to RSA Encryption in the Quantum Era

Shafeeq Rahman Thottoli, Musfar Muhamed Kozhikkal

Quantum computing has raised significant concerns regarding the security of classical cryptographic systems, particularly RSA, as it depends on the computational difficulty of factoring large semiprime numbers.In this study, we demonstrate the practical application of Shor's algorithm by successfully factorizing a semiprime integer, up to 30 bits (857830637 = 29167 X 29411) using the QuantumRings simulator.Our work highlights the effectiveness of Shor's algorithm in solving the factorization problem in polynomial time, which will significantly improve over the classical method for a large number.The results suggest that with advances in quantum hardware, such as increasing qubit counts and improving error correction, breaking larger RSA keys (e.g., RSA-2048) may soon become feasible.This seriously threatens current cryptographic systems, emphasizing the need to adopt post-quantum cryptography.Our findings aim to raise awareness among researchers, policymakers, and industry leaders of the importance of preparing for a quantum-safe future.

International Journal of Science and Research (IJSR)•Apr 22, 2025•0 citations

Improving the success rate of quantum algorithm attacking RSA encryption system

Yumin Dong, Hengrui Liu, Yanying Fu +4 more

Shor’s factorization algorithm (SFA) aims at finding the non-trivial factor of a given composite number, but the algorithm does not always work. In some cases, it has to call back to the beginning of the algorithm to make recalculation. After the analysis of the principle of SFA and the characteristics of RSA public-key cryptography with a series of data calculations, it can be concluded that the random value selected by the algorithm is closely related to whether the obtained period is effective. Therefore, a new optimized scheme is proposed to tackle with this defect from two perspectives: (a) When the a value is a perfect square, the algorithm can be completed with an odd cycle r. (b) When the period r obtained by the randomly selected a value is a multiple of 3, the algorithm can be completed by modifying the decomposition method to relax the requirements for the period without affecting the complexity of the algorithm. Due to the limitations of hardware in applying the quantum algorithms, the classical algorithm is applied to simulate quantum algorithms to test the success rate of decomposition of some composite numbers. The result indicates the effectiveness of the improved algorithm, which significantly reduces the probability of repeated operations to save the quantum circuit resources.

Journal of Applied Physics•Jul 10, 2023•7 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

Shor’s factoring algorithm and modern cryptography. An illustration of the capabilities inherent in quantum computers

E. Gerjuoy

The security of messages encoded via the widely used RSA public key encryption system rests on the enormous computational effort required to find the prime factors of a large number N using classical (conventional) computers. In 1994 Peter Shor showed that for sufficiently large N, a quantum computer could perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the nonexpert, the RSA encryption protocol; the various quantum computer manipulations constituting the Shor algorithm; how the Shor algorithm performs the factoring; and the precise sense in which a quantum computer employing Shor’s algorithm can be said to accomplish the factoring of very large numbers with less computational effort than a classical computer. It is made apparent that factoring N generally requires many successive runs of the algorithm. Our analysis reveals that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.

arXiv:quant-ph/0411184•American Journal of Physics•May 13, 2005•101 citations

Using Single Time of Quantum Computer for Shor's Factoring Algorithm

Yousef Alhammadi

Peter Shor's in 1994 developed a factoring algorithm that can factor a composite number$\boldsymbol{n}$in a polynomial time by using a quantum computer in one step of the algorithm. The algorithm may contain a loop that requires calling a quantum computer many times to find the order of selected number$a, a\in Z_{n}$. In this paper, the improvement to the Shor's factoring algorithm guarantees the single use of the quantum computer to find the order, where the rest of the algorithm can be implemented by a classical computer. A numerical example for the original and improved version is presented.

International Conference on IT Innovation and Knowledge Discovery (ITIKD)•Mar 8, 2023•0 citations

Exploring Shor's Algorithm in Cracking RSA Encryption

Aashutosh Srivastava

The present study explores the groundbreaking possibilities of Shor's algorithm in cracking RSA encryption, hence enhancing the security consequences of this extensively employed cryptographic protocol. Due to Shor's algorithm's exponential speed advantage over classical algorithms, RSA encryption—a popular public key cryptosystem—is vulnerable to quantum attacks. To keep its security, RSA depends on the difficulty of factoring huge semi-primes. RSA's security presumptions are called into question by Shor's algorithm's quick factorization on a quantum computer, which has prompted research into post-quantum cryptography solutions to guarantee secure communication in the quantum age. Even with parallel computation, the speed and storage capacity of classical computing are constrained. A key idea in quantum computing is quantum parallelism, which allows quantum systems to carry out several computations at once. In contrast to classical portions. The scope of this paper is to understand the fundamentals of Quantum Computing, the current state of Shor’s algorithm implementation, and efficiency, particularly its application in compromising public key cryptosystems like RSA. The project aims to achieve how factorization is done through classical methods and further, how is this done through Shor’s algorithm and QFT techniques.

International Journal of Sciences: Basic and Applied Research•Nov 15, 2024•0 citations
Shor's factoring algorithm (SFA), by its ability to efficiently factor large numbers, has the potential to undermine contemporary encryption. At its heart is a process called order finding, which quantum mechanics lets us perform efficiently. SFA thus consists of a \emph{quantum order finding algorithm} (QOFA), bookended by classical routines which, given the order, return the factors. But, with probability up to 1/21/21/2, these classical routines fail, and QOFA must be rerun. We modify these routines using elementary results in number theory, improving the likelihood that they return the factors. The resulting quantum factoring algorithm is better than SFA at factoring safe semiprimes, an important class of numbers used in cryptography. With just one call to QOFA, our algorithm almost always factors safe semiprimes. As well as a speed-up, improving efficiency gives our algorithm other, practical advantages: unlike SFA, it does not need a randomly picked input, making it simpler to construct in the lab; and in the (unlikely) case of failure, the same circuit can be rerun, without modification. We consider generalizing this result to other cases, although we do not find a simple extension, and conclude that SFA is still the best algorithm for general numbers (non safe semiprimes, in other words). Even so, we present some simple number theoretic tricks for improving SFA in this case.
Quantum computing has raised significant concerns regarding the security of classical cryptographic systems, particularly RSA, as it depends on the computational difficulty of factoring large semiprime numbers.In this study, we demonstrate the practical application of Shor's algorithm by successfully factorizing a semiprime integer, up to 30 bits (857830637 = 29167 X 29411) using the QuantumRings simulator.Our work highlights the effectiveness of Shor's algorithm in solving the factorization problem in polynomial time, which will significantly improve over the classical method for a large number.The results suggest that with advances in quantum hardware, such as increasing qubit counts and improving error correction, breaking larger RSA keys (e.g., RSA-2048) may soon become feasible.This seriously threatens current cryptographic systems, emphasizing the need to adopt post-quantum cryptography.Our findings aim to raise awareness among researchers, policymakers, and industry leaders of the importance of preparing for a quantum-safe future.
Shor’s factorization algorithm (SFA) aims at finding the non-trivial factor of a given composite number, but the algorithm does not always work. In some cases, it has to call back to the beginning of the algorithm to make recalculation. After the analysis of the principle of SFA and the characteristics of RSA public-key cryptography with a series of data calculations, it can be concluded that the random value selected by the algorithm is closely related to whether the obtained period is effective. Therefore, a new optimized scheme is proposed to tackle with this defect from two perspectives: (a) When the a value is a perfect square, the algorithm can be completed with an odd cycle r. (b) When the period r obtained by the randomly selected a value is a multiple of 3, the algorithm can be completed by modifying the decomposition method to relax the requirements for the period without affecting the complexity of the algorithm. Due to the limitations of hardware in applying the quantum algorithms, the classical algorithm is applied to simulate quantum algorithms to test the success rate of decomposition of some composite numbers. The result indicates the effectiveness of the improved algorithm, which significantly reduces the probability of repeated operations to save the quantum circuit resources.
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.
The security of messages encoded via the widely used RSA public key encryption system rests on the enormous computational effort required to find the prime factors of a large number N using classical (conventional) computers. In 1994 Peter Shor showed that for sufficiently large N, a quantum computer could perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the nonexpert, the RSA encryption protocol; the various quantum computer manipulations constituting the Shor algorithm; how the Shor algorithm performs the factoring; and the precise sense in which a quantum computer employing Shor’s algorithm can be said to accomplish the factoring of very large numbers with less computational effort than a classical computer. It is made apparent that factoring N generally requires many successive runs of the algorithm. Our analysis reveals that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.
Peter Shor's in 1994 developed a factoring algorithm that can factor a composite numbern\boldsymbol{n}nin a polynomial time by using a quantum computer in one step of the algorithm. The algorithm may contain a loop that requires calling a quantum computer many times to find the order of selected numbera,a∈Zna, a\in Z_{n}a,a∈Zn​. In this paper, the improvement to the Shor's factoring algorithm guarantees the single use of the quantum computer to find the order, where the rest of the algorithm can be implemented by a classical computer. A numerical example for the original and improved version is presented.
The present study explores the groundbreaking possibilities of Shor's algorithm in cracking RSA encryption, hence enhancing the security consequences of this extensively employed cryptographic protocol. Due to Shor's algorithm's exponential speed advantage over classical algorithms, RSA encryption—a popular public key cryptosystem—is vulnerable to quantum attacks. To keep its security, RSA depends on the difficulty of factoring huge semi-primes. RSA's security presumptions are called into question by Shor's algorithm's quick factorization on a quantum computer, which has prompted research into post-quantum cryptography solutions to guarantee secure communication in the quantum age. Even with parallel computation, the speed and storage capacity of classical computing are constrained. A key idea in quantum computing is quantum parallelism, which allows quantum systems to carry out several computations at once. In contrast to classical portions. The scope of this paper is to understand the fundamentals of Quantum Computing, the current state of Shor’s algorithm implementation, and efficiency, particularly its application in compromising public key cryptosystems like RSA. The project aims to achieve how factorization is done through classical methods and further, how is this done through Shor’s algorithm and QFT techniques.