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

Continued Fractions and Probability Estimations in the Shor Algorithm -- A Detailed and Self-Contained Treatise

Johanna Barzen, Frank Leymann

Published May 4, 2022• 0 citations
arXivHTMLPDF

Abstract

The algorithm of Shor for prime factorization is a hybrid algorithm consisting of a quantum part and a classical part. The main focus of the classical part is a continued fraction analysis. The presentation of this is often short, pointing to text books on number theory. In this contribution, we present the relevant results and proofs from the theory of continued fractions in detail (even in more detail than in text books) filling the gap to allow a complete comprehension of the algorithm of Shor. Similarly, we provide a detailed computation of the estimation of the probability that convergents will provide the period required for determining a prime factor.

DOI
10.48550/arxiv.2205.01925

Related papers

Continued Fractions and Probability Estimations in Shor’s Algorithm: A Detailed and Self-Contained Treatise

Johanna Barzen, Frank Leymann

Shor’s algorithm for prime factorization is a hybrid algorithm consisting of a quantum part and a classical part. The main focus of the classical part is a continued fraction analysis. The presentation of this is often short, pointing to text books on number theory. In this contribution, we present the relevant results and proofs from the theory of continued fractions in detail (even in more detail than in text books), filling the gap to allow a complete comprehension of Shor’s algorithm. Similarly, we provide a detailed computation of the estimation of the probability that convergents will provide the period required for determining a prime factor.

AppliedMath•Jul 18, 2022•4 citations

Recovering the Period in Shor's Algorithm with Gauss' Algorithm for Lattice Basis Reduction

Allison Koenecke, Paweł Wocjan

Shor's algorithm contains a classical post-processing part for which we aim to create an efficient, understandable method aside from continued fractions. Let r be an unknown positive integer. Assume that with some constant probability we obtain random positive integers of the form x=[ N k/r ] where [.] is either the floor or ceiling of the rational number, k is selected uniformly at random from {0,1,...,r-1}, and N is a parameter that can be chosen. The problem of recovering r from such samples occurs precisely in the classical post-processing part of Shor's algorithm. The quantum part (quantum phase estimation) makes it possible to obtain such samples where r is the order of some element a of the unit group of Z_n and n is the number to be factored. Shor showed that the continued fraction algorithm can be used to efficiently recover r, since if N>2r^2 then k/r appears in lowest terms as one of the convergents of x/N due to a standard result on continued fractions. We present here an alternative method for recovering r based on the Gauss algorithm for lattice basis reduction, allowing us to efficiently find the shortest nonzero vector of a lattice generated by two vectors. Our method is about as efficient as the method based on continued fractions, yet it is much easier to understand all the details of why it works.

arXiv:1210.3003•Oct 10, 2012•2 citations

Shor's Algorithm

Richard J. Lipton, Kenneth W. Regan

This chapter contains sections titled: 11.1 Strategy, 11.2 Good Numbers, 11.3 Quantum Part of the Algorithm, 11.4 Analysis of the Quantum Part, 11.5 Probability of a Good Number, 11.6 Using a Good Number, 11.7 Continued Fractions, 11.8 Problems, 11.9 Summary and Notes

•Jan 1, 2014•1 citation

Shor's Factoring Algorithm and Modular Exponentiation Operators

Robert Singleton

We provide a pedagogical presentation of Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time. In contrast, all known classical algorithms for the factoring problem take an exponential time to factor such large numbers. Shor's algorithm therefore has profound implication for public-key encryption such as RSA and Diffie–Hellman key exchange. We assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing. Shor's algorithm contains a number of moving parts, and can be rather daunting at first. The literature is replete with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation. They require a thicket of appendices and assume a knowledge of quantum algorithms and classical mathematics with which the reader might not be familiar. We therefore start with first principle derivations of the quantum Fourier transform (QFT) and quantum phase estimation (QPE), which are the essential building blocks of Shor's algorithm. We then go on to develop the theory of modular exponentiation (ME) operators, one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. We also delve into the number theory that establishes the link between factorization and the period of the modular exponential function. We then apply the QPE algorithm to obtain Shor's factoring algorithm. We also discuss the post-quantum processing and the method of continued fractions, which is used to extract the exact period of the modular exponential function from the approximately measured phase angles of the ME operator. The manuscript then moves on to a series of examples. We first verify the formalism by factoring N=15, the smallest number accessible to Shor's algorithm. We then proceed to factor larger integers, developing a systematic procedure that will find the ME operators for any semi-prime N=p×q (where q and p are prime). Finally, we factor the composite numbers N=21, 33, 35, 143, 247 using the Qiskit simulator. It is observed that the ME operators are somewhat forgiving, and truncated approximate forms are able to extract factors just as well as the exact operators. This is because the method of continued fractions only requires an approximate phase value for its input, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. Quanta 2023; 12: 41–130.

arXiv:2306.09122•Quanta•Sep 15, 2023•8 citations

Shor Factoring Algorithm and the Quantum Fourier Transform

Alice Flarend, Robert Hilborn

Abstract Expanding on the factoring and periodicity in Chapter 14, the Shor algorithm is explained in detail, with a warning that this is one of the toughest chapters in the book. While the steps of Shor algorithm may look just like the RSA in reverse, the quantum computer is needed to find the periodicity of the factors and thereby the prime factors themselves. Fourier analysis is the tool for this. The quantum Fourier transform is described, including the quantum circuit, after first showing what the classical Fourier transform accomplishes. Extensive examples of all the steps are given.

•Jul 9, 2026•0 citations

Shor's Factoring Algorithm and Modern Cryptography. An Illustration of the Capabilities Inherent in Quantum Computers

Gerjuoy, E

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 (i.e., conventional) computers. In 1994, however, Peter Shor showed that for sufficiently large N a quantum computer would be expected to perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the non-expert readers of this journal: (i) the RSA encryption protocol; (ii) the various quantum computer manipulations constituting the Shor algorithm; (iii) how the Shor algorithm performs the factoring; and (iv) 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 can. It is made apparent that factoring $N$ generally requires many successive runs of the algorithm. The careful analysis herein reveals, however, that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.

•Nov 25, 2004•50 citations
The algorithm of Shor for prime factorization is a hybrid algorithm consisting of a quantum part and a classical part. The main focus of the classical part is a continued fraction analysis. The presentation of this is often short, pointing to text books on number theory. In this contribution, we present the relevant results and proofs from the theory of continued fractions in detail (even in more detail than in text books) filling the gap to allow a complete comprehension of the algorithm of Shor. Similarly, we provide a detailed computation of the estimation of the probability that convergents will provide the period required for determining a prime factor.
Shor’s algorithm for prime factorization is a hybrid algorithm consisting of a quantum part and a classical part. The main focus of the classical part is a continued fraction analysis. The presentation of this is often short, pointing to text books on number theory. In this contribution, we present the relevant results and proofs from the theory of continued fractions in detail (even in more detail than in text books), filling the gap to allow a complete comprehension of Shor’s algorithm. Similarly, we provide a detailed computation of the estimation of the probability that convergents will provide the period required for determining a prime factor.
Shor's algorithm contains a classical post-processing part for which we aim to create an efficient, understandable method aside from continued fractions. Let r be an unknown positive integer. Assume that with some constant probability we obtain random positive integers of the form x=[ N k/r ] where [.] is either the floor or ceiling of the rational number, k is selected uniformly at random from {0,1,...,r-1}, and N is a parameter that can be chosen. The problem of recovering r from such samples occurs precisely in the classical post-processing part of Shor's algorithm. The quantum part (quantum phase estimation) makes it possible to obtain such samples where r is the order of some element a of the unit group of Z_n and n is the number to be factored. Shor showed that the continued fraction algorithm can be used to efficiently recover r, since if N>2r^2 then k/r appears in lowest terms as one of the convergents of x/N due to a standard result on continued fractions. We present here an alternative method for recovering r based on the Gauss algorithm for lattice basis reduction, allowing us to efficiently find the shortest nonzero vector of a lattice generated by two vectors. Our method is about as efficient as the method based on continued fractions, yet it is much easier to understand all the details of why it works.
We provide a pedagogical presentation of Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time. In contrast, all known classical algorithms for the factoring problem take an exponential time to factor such large numbers. Shor's algorithm therefore has profound implication for public-key encryption such as RSA and Diffie–Hellman key exchange. We assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing. Shor's algorithm contains a number of moving parts, and can be rather daunting at first. The literature is replete with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation. They require a thicket of appendices and assume a knowledge of quantum algorithms and classical mathematics with which the reader might not be familiar. We therefore start with first principle derivations of the quantum Fourier transform (QFT) and quantum phase estimation (QPE), which are the essential building blocks of Shor's algorithm. We then go on to develop the theory of modular exponentiation (ME) operators, one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. We also delve into the number theory that establishes the link between factorization and the period of the modular exponential function. We then apply the QPE algorithm to obtain Shor's factoring algorithm. We also discuss the post-quantum processing and the method of continued fractions, which is used to extract the exact period of the modular exponential function from the approximately measured phase angles of the ME operator. The manuscript then moves on to a series of examples. We first verify the formalism by factoring N=15, the smallest number accessible to Shor's algorithm. We then proceed to factor larger integers, developing a systematic procedure that will find the ME operators for any semi-prime N=p×q (where q and p are prime). Finally, we factor the composite numbers N=21, 33, 35, 143, 247 using the Qiskit simulator. It is observed that the ME operators are somewhat forgiving, and truncated approximate forms are able to extract factors just as well as the exact operators. This is because the method of continued fractions only requires an approximate phase value for its input, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. Quanta 2023; 12: 41–130.
Abstract Expanding on the factoring and periodicity in Chapter 14, the Shor algorithm is explained in detail, with a warning that this is one of the toughest chapters in the book. While the steps of Shor algorithm may look just like the RSA in reverse, the quantum computer is needed to find the periodicity of the factors and thereby the prime factors themselves. Fourier analysis is the tool for this. The quantum Fourier transform is described, including the quantum circuit, after first showing what the classical Fourier transform accomplishes. Extensive examples of all the steps are given.
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 (i.e., conventional) computers. In 1994, however, Peter Shor showed that for sufficiently large N a quantum computer would be expected to perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the non-expert readers of this journal: (i) the RSA encryption protocol; (ii) the various quantum computer manipulations constituting the Shor algorithm; (iii) how the Shor algorithm performs the factoring; and (iv) 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 can. It is made apparent that factoring NNN generally requires many successive runs of the algorithm. The careful analysis herein reveals, however, that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.