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

Order finding, period finding, and quantum factoring

Steven Herbert

Published Dec 8, 2025• 0 citations
Publisher

Abstract

Abstract Peter Shor’s quantum factoring algorithm is one of the crowning achievements of the field of quantum computation and information. This chapter shows how quantum computing offers a super-polynomial (i.e., nearly exponential) advantage for the order-finding problem relative to the best-known classical counterpart, which can then be applied to the problem of factoring. Not only is this the most celebrated result in theoretical quantum computer science, but it also has the seismic implication that if and when quantum computing becomes a reality, the vast number of cryptosystems built on the the Rivest–Shamir–Adleman cryptosystem (RSA) protocol will no longer be secure.

DOI
10.1093/9780191964381.003.0010

Related papers

An Exposition on Peter Shor's Polynomial-Time Factoring Algorithm and Its Effects on Post-Quantum Cryptography

Kristopher Lonnie Watkins

When building cryptosystems, cryptographers focus on finding problems that are not believed to be solvable in polynomial-time. Some of the most popular problems they have found are the Discrete Logarithm Problem and Integer Factoring. The former is used in Diffie-Hellman Key Exachange (DHK) and El Gamal encryption, while the latter is used in RSA. El Gamal and DHK are both very popular, but RSA is more prevalent due to its efficiency.\n Nevertheless, it is plausible that in the next few decades, all three of these systems will likely be useless due to the advances made by Peter Shor in quantum computing. This paper will explain the details of how Shor’s algorithm works and how it accomplishes the above. It will also feature a redesign of the proof of Jeffrey Miller (1975) that efficiently reduces from order finding in a group of order N to factoring N. Hopefully, doing so will aid future students in their studies of quantum algorithms and Post-Quantum Cryptography.

•Oct 30, 2019•0 citations

Implementation of Shor’s Algorithm in QISKIT by Quantum Computing using IBMQ

Quantum machine learning is the combination of quantum computing and classical machine learning. It helps in solving the problems of one field to another field. Shor’s algorithm is used for factoring the integers in polynomial time. Since the bestknown classical algorithm requires super polynomial time to factor the product of two primes, the widely used cryptosystem, RSA, relies on factoring being impossible for large enough integers. In this paper we will focus on the quantum part of Shor’s algorithm, which actually solves the problem of period finding. In polynomial time factoring problem can be turned into a period finding problem so an efficient period finding algorithm can be used to factor integers efficiently.

International Journal of Advanced Trends in Computer Science and Engineering•Apr 5, 2021•0 citations

Quantum Computing

Susan Loepp, William K. Wootters

Introduction In an ordinary computer, information is stored in a collection of tiny circuits each of which is designed to have two stable and easily distinguishable configurations: each represents a bit . In our study of quantum cryptography, we have seen how it can be useful to express information not in ordinary bits but in qubits . Whereas a bit can have only two values, say 0 and 1, a qubit can be in any quantum superposition of ∣0〉 and ∣1〉. Moreover, a qubit can be entangled with other qubits. Thus one might wonder whether a quantum computer, in which the basic elements for storing and processing information are qubits, can outperform an ordinary (classical) computer in certain ways. This question was addressed by researchers starting in the 1980s. In terms of practical consequences, perhaps the most dramatic answer has been given by Peter Shor in his 1994 factoring algorithm for a quantum computer, an algorithm that is exponentially faster than any known classical algorithm. As we have seen in Chapter 1, the difficulty of factoring a product of two large primes is the basis of the security of the RSA cryptosystem. So if one could build a large enough quantum computer – and there is no reason in principle why this could not be done – the RSA system would be rendered ineffective. In this chapter we present the basics of quantum computation and then focus on Shor's factoring algorithm.

Cambridge University Press eBooks•Jul 10, 2006•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

Qubits and quantum dots

Yuli V. Nazarov, Yaroslav M. Blanter

It is difficult nowadays to graduate from a department of natural sciences and not hear anything about quantum computing, most likely about the fascinating prospects of it. Quantum computing by its origin is a rather abstract discipline, a branch of math or information science. It has emerged from a persistent search for more efficient ways to process information when quantum mechanics made it to the scope of the search. Being an abstract discipline, quantum computing approximates a physical quantum system with a number of axioms and explores the consequences of these axioms, precisely as conventional math has been. These activities begun in the 1970s, and for a long time it was not obvious why quantum calculational schemes have to be any better than common computer algorithms. This extensive work was rewarded with a break-through in 1994, when Peter Shor discovered a remarkable quantum algorithm for the factorization of large numbers into prime ones. This sounds quite abstract, but many public key cryptosystems will become obsolete if Shor's algorithm is ever implemented in a practical quantum computer. Modern communication security is based on the fact that the factorization is a tough problem for a classical computer: it takes too long to crack a code. The proposed algorithm speeds up the factorization enormously. The discovery by Shor has brought quantum computing to the scientific and even public attention. This progress has motivated a massive research effort towards the manipulation of individual quantum systems, the practical realization of quantum computing schemes being one of the most attractive goals. This chapter describes this goal, the quantum transport systems suitable for it, and the achievements made so far.

Cambridge University Press eBooks•May 28, 2009•0 citations

Implementation of Shor's Algorithm and Reliability of Quantum Computing Devices

Maria E. Sabani, Ilias Galanis, Ilias Κ. Savvas +1 more

The process to find the prime factors of a large number, the “factoring problem” is believed to be a very hard problem. For this reason, it is the cornerstone of modern cryptographic schemes, like RSA cryptosystem. In 1994, Professor Peter Shor proposed a new polynomial-time quantum algorithm that finds the prime factors of a number with many digits. This was a bolt from the blue for the security of transactions and electronic communications and became an example of how quantum computing changes our perception of security and safety. In this paper Shor's Algorithm is presented and an implementation, a way to factor number 21 is described. In addition, some reliability issues of quantum devices were considered in order to explore the potentiality of Shor's algorithm.

Panhellenic Conference on Informatics•Nov 26, 2021•6 citations
Abstract Peter Shor’s quantum factoring algorithm is one of the crowning achievements of the field of quantum computation and information. This chapter shows how quantum computing offers a super-polynomial (i.e., nearly exponential) advantage for the order-finding problem relative to the best-known classical counterpart, which can then be applied to the problem of factoring. Not only is this the most celebrated result in theoretical quantum computer science, but it also has the seismic implication that if and when quantum computing becomes a reality, the vast number of cryptosystems built on the the Rivest–Shamir–Adleman cryptosystem (RSA) protocol will no longer be secure.
When building cryptosystems, cryptographers focus on finding problems that are not believed to be solvable in polynomial-time. Some of the most popular problems they have found are the Discrete Logarithm Problem and Integer Factoring. The former is used in Diffie-Hellman Key Exachange (DHK) and El Gamal encryption, while the latter is used in RSA. El Gamal and DHK are both very popular, but RSA is more prevalent due to its efficiency.\n Nevertheless, it is plausible that in the next few decades, all three of these systems will likely be useless due to the advances made by Peter Shor in quantum computing. This paper will explain the details of how Shor’s algorithm works and how it accomplishes the above. It will also feature a redesign of the proof of Jeffrey Miller (1975) that efficiently reduces from order finding in a group of order N to factoring N. Hopefully, doing so will aid future students in their studies of quantum algorithms and Post-Quantum Cryptography.
Quantum machine learning is the combination of quantum computing and classical machine learning. It helps in solving the problems of one field to another field. Shor’s algorithm is used for factoring the integers in polynomial time. Since the bestknown classical algorithm requires super polynomial time to factor the product of two primes, the widely used cryptosystem, RSA, relies on factoring being impossible for large enough integers. In this paper we will focus on the quantum part of Shor’s algorithm, which actually solves the problem of period finding. In polynomial time factoring problem can be turned into a period finding problem so an efficient period finding algorithm can be used to factor integers efficiently.
Introduction In an ordinary computer, information is stored in a collection of tiny circuits each of which is designed to have two stable and easily distinguishable configurations: each represents a bit . In our study of quantum cryptography, we have seen how it can be useful to express information not in ordinary bits but in qubits . Whereas a bit can have only two values, say 0 and 1, a qubit can be in any quantum superposition of ∣0〉 and ∣1〉. Moreover, a qubit can be entangled with other qubits. Thus one might wonder whether a quantum computer, in which the basic elements for storing and processing information are qubits, can outperform an ordinary (classical) computer in certain ways. This question was addressed by researchers starting in the 1980s. In terms of practical consequences, perhaps the most dramatic answer has been given by Peter Shor in his 1994 factoring algorithm for a quantum computer, an algorithm that is exponentially faster than any known classical algorithm. As we have seen in Chapter 1, the difficulty of factoring a product of two large primes is the basis of the security of the RSA cryptosystem. So if one could build a large enough quantum computer – and there is no reason in principle why this could not be done – the RSA system would be rendered ineffective. In this chapter we present the basics of quantum computation and then focus on Shor's factoring algorithm.
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.
It is difficult nowadays to graduate from a department of natural sciences and not hear anything about quantum computing, most likely about the fascinating prospects of it. Quantum computing by its origin is a rather abstract discipline, a branch of math or information science. It has emerged from a persistent search for more efficient ways to process information when quantum mechanics made it to the scope of the search. Being an abstract discipline, quantum computing approximates a physical quantum system with a number of axioms and explores the consequences of these axioms, precisely as conventional math has been. These activities begun in the 1970s, and for a long time it was not obvious why quantum calculational schemes have to be any better than common computer algorithms. This extensive work was rewarded with a break-through in 1994, when Peter Shor discovered a remarkable quantum algorithm for the factorization of large numbers into prime ones. This sounds quite abstract, but many public key cryptosystems will become obsolete if Shor's algorithm is ever implemented in a practical quantum computer. Modern communication security is based on the fact that the factorization is a tough problem for a classical computer: it takes too long to crack a code. The proposed algorithm speeds up the factorization enormously. The discovery by Shor has brought quantum computing to the scientific and even public attention. This progress has motivated a massive research effort towards the manipulation of individual quantum systems, the practical realization of quantum computing schemes being one of the most attractive goals. This chapter describes this goal, the quantum transport systems suitable for it, and the achievements made so far.
The process to find the prime factors of a large number, the “factoring problem” is believed to be a very hard problem. For this reason, it is the cornerstone of modern cryptographic schemes, like RSA cryptosystem. In 1994, Professor Peter Shor proposed a new polynomial-time quantum algorithm that finds the prime factors of a number with many digits. This was a bolt from the blue for the security of transactions and electronic communications and became an example of how quantum computing changes our perception of security and safety. In this paper Shor's Algorithm is presented and an implementation, a way to factor number 21 is described. In addition, some reliability issues of quantum devices were considered in order to explore the potentiality of Shor's algorithm.