References for Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer

This informal paper lists online, free references which I have consulted in my quest to deeply comprehend Shor’s algorithm for using a quantum computer to factor large semiprime integers such as used for public key encryption.

This list of references was originally part of my informal paper Some Preliminary Questions About Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer, but I moved them here as a standalone paper since they have value separate from that specific paper.

General notes

First, some general notes. More specific or technical notes are given on specific reference citations.

  1. I won’t suggest that these references are an ideal roadmap for others seeking to comprehend Shor’s algorithm at a deep level, but they are decent jumping-off points depending on your particular interests.
  2. I haven’t found any of these references to be truly comprehensive. They each have bits and pieces of the overall algorithm, rarely the same bits and pieces, and always failing to present the entire, complete picture to a sufficient level of depth — for my tastes, at least.
  3. My goal is to gain a comprehensive, deep, and intuitive grasp of Shor’s algorithm, not simply a rote mechanical recitation of its steps as a recipe. Strong emphasis on intuition.
  4. I still have quite a few gaps in my comprehension of Shor’s algorithm, as detailed in my previously cited paper, Some Preliminary Questions About Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer. It’s not that I don’t have any knowledge for these gaps, but that I don’t have absolute 100% confidence and strong intuition for these gaps.
  5. Maybe to an expert in number theory the gaps between the bits and pieces are obvious, but I’m no expert in number theory.
  6. Actual implementations of Shor’s algorithm are included as well, especially when a GitHub repository is used.
  7. Derivatives of Shor’s original algorithm are also included. It is not uncommon for implementations to be based on derivatives rather than the original algorithm.
  8. Some alternatives to Shor’s algorithm are also listed, although that was not a priority here.
  9. The ultimate goal is Shor’s algorithm running on a physical quantum computer, but most of the efforts so far have used quantum simulators due to lack of qubits and insufficient coherence time. To the best of my knowledge the largest semiprimes factored to date on a physical quantum computer are 15 and 21, and these did not use the pure Shor’s algorithm as originally published.
  10. I don’t have any coverage for the second part of Shor’s original paper, computing discrete logarithms.
  11. Generally, textbooks and other books are not cited as references here since they tend not to be online (other than illegal, bootleg copies!) and free. I personally require online, free materials. But a brief list of books known to have relevant coverage of Shor’s algorithm is found after the main list of references.
  12. This list is not intended to necessarily be exhaustive or fully comprehensive, but reasonably thorough. I will add to it as I discover additional references.
  13. At present, the reference citations are in no particular order, typically chronologically in the order I added them.

My own, informal papers

First, my own, informal papers which relate to Shor’s algorithm:

  1. Some Preliminary Questions About Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer. Details of my own personal gaps of knowledge.
  2. Ingredients for Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer. An approximation of a summary of Shor’s algorithm.


Now, the list of reference citations:

  1. Shor’s original paper — Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
  2. Wikipedia Shor’s algorithm article —
  3. Riemann’s Hypothesis and Tests for Primality by Miller (1976) — Referenced by Shor’s original paper — “It is known that using randomization, factorization can be reduced to finding the order of an element [Miller 1976]”. Assumes the Extended Riemann Hypothesis (ERH). This is really the heart and soul of the clever trick that make Shor’s algorithm work.
  4. MultiplicativeOrder by Wolfram — Multiplicative order is the more proper term for order finding, which is at the heart of Shor’s algorithm.
  5. Scott Aaronson’s blog post — Shor, I’ll do it
  6. Wikipedia Integer factorization article —
  7. Wikipedia Semiprime article —
  8. Wolfram MathWorld definition of Semiprime
  9. Quantum Algorithm Zoo
  10. Wikipedia Chinese remainder theorem article —
  11. Wikipedia Euler’s theorem article —
  12. Wikipedia Euler’s totient function
  13. What Has Quantum Mechanics to Do With Factoring? — Things I wish they had told me about Peter Shor’s algorithm by N. David Mermin —
  14. The Quantum States of Shor’s Algorithm by Neal Young of Dartmouth —
  15. Shor’s Algorithm for Factoring Large Integers by Lavor, Manssur, and Portugal —
  16. Shor’s Quantum Factoring Algorithm by Lomonaco —
  17. Computational Complexity: A Modern Approach — Chapter 20 Quantum Computation by Arora and Barak —
  18. Quantum computation: a tutorial by Braunstein —
  19. Circuit for Shor’s algorithm using 2n+3 qubits paper by Beauregard — One of the derivative algorithms.
  20. Fast Quantum Modular Exponentiation Architecture for Shor’s Factorization Algorithm paper by Pavlidis and Gizopoulos — Requires 9n + 3 qubits, but fewer gate executions. Another derivative algorithm.
  21. Quantum factorization of 56153 with only 4 qubits paper by Dattani and Bryans — An alternative algorithm.
  22. Shor’s Algorithm Simulator “This page simulates Shor’s Algorithm for integer factorization with a quantum computer. Since this page runs in javascript on your non-quantum browser, the quantum part of the algorithm is simulated using probabilities.” Interesting.
  23. Shor’s order (period) finding algorithm and factoring — C/CS/Phys 191 11/01/05 — Fall 2005 Lecture 19 notes
  24. Shor’s Algorithm for Factoring Large Integers paper by Lavor, Manssur, and Portugal — “This work is a tutorial on Shor’s factoring algorithm by means of a worked out example. Some basic concepts of Quantum Mechanics and quantum circuits are reviewed. It is intended for non-specialists which have basic knowledge on undergraduate Linear Algebra.
  25. Factoring Safe Semiprimes with a Single Quantum Query paper by Grosshans, Lawson, Morain, and Smith — “With just one call to QOFA [quantum order finding algorithm], our algorithm almost always factors safe semiprimes.” A variation on Shor’s algorithm, not a straight derivative but not a true alternative either — still uses the concept of order finding, which is at the heart of Shor’s algorithm.
  26. Alas, I am unable to give the Quantum Computation and Quantum Information book by Nielsen and Chuang as a reference for my work since I am limiting myself to online free material. See and
  27. IBM Q Experience documentation — Shor’s algorithm's_algorithm.html.
  28. NIST Post-Quantum Cryptography effort —
  29. Wikipedia Post-quantum cryptography article —
  30. A quantum algorithm for greatest common divisor problem paper by Wang, Jiang, Mu, and Fan —
  31. Shor’s Algorithm presentation by Bäumer, Sobez, and Tessarini
  32. Shor’s Algorithm and the Quantum Fourier Transform by Fang Xi Lin of McGill University — An alternative description of Shor’s algorithm, but still doesn’t answer most of my questions. I used it to try to understand the quantum Fourier transform a little better, but my questions persist.
  33. Scaling laws for Shor’s algorithm with a banded quantum Fourier transform by Nam and Blümel — An alternative description of Shor’s algorithm as well as an adaptation using a banded QFT for much better performance.
  34. Symmetry boosts quantum computer performance by Nam and Blümel — Yet another adaptation of Shor’s algorithm to boost performance.
  35. Quantum Computing Lecture Notes by Mark Oskin of University of Washington — Yet another description of Shor’s algorithm, order-finding, QFT, phase estimation, and quantum computing in general.
  36. CSE 599d — Quantum Computing — Shor’s Algorithm lecture notes by Dave Bacon, Department of Computer Science & Engineering, University of Washington —
  37. Experimental Realization of an Order-Finding Algorithm with an NMR Quantum Computer by Vandersypen, Steffen, Breyta, Yannoni, Cleve, and Chuang of IBM Almaden Research Center and Stanford — Early implementation (2000) of order-finding algorithm using a nuclear magnetic resonance (NMR) quantum computer. A custom molecule implemented a 5-qubit quantum computer.
  38. Quantum Algorithm Implementations for Beginners by Coles, Eidenbenz, Pakin, et al — Includes a reasonably succinct description of Shor’s algorithm including an implementation on the IBM ibmqx4 5-qubit quantum computer. Still leaves many questions unanswered. They factored 15 using a selected random number of 11. The raw algorithm required 12 qubits and 196 gates, so they used an optimized/compiled version which worked in 5 qubits and 11 gates. Seems like cheating, to me.
  39. A Re-evaluation of Shor’s Algorithm by Cooper — Critical examination of Shor’s algorithm. But still leaves many questions and issues unanswered. Vintage 2006.
  40. Shor’s Algorithm in Pyquil by Alec Brickner — Student project for CS 269Q: Quantum Computer Programming course at Stanford.
  41. Implementation of Shor’s algorithm in pyQuil by William Burton — Student project for CS 269Q: Quantum Computer Programming course at Stanford.
  42. Realization of a scalable Shor algorithm by Monz, Nigg, Martinez, Brandl, Schindler, Rines, Wang, Chuang, and Blatt — Factored 15 using a trapped-ion quantum computer with seven qubits. Technically, this is a derivative of Shor’s algorithm, not the exact same algorithm as originally published by Shor.
  43. Variational Quantum Factoring by Anschuetz, Olson, Aspuru-Guzik, and Cao — An alternative approach using QAOA (Quantum Approximate Optimization Algorithm), which is not based on Shor’s approach. On December 11, 2019 Zapata Computing and IBM announced (via Twitter) that they had factored 1099551473989 (1048589 x 1048601) using three qubits with a solution found 30% of the time, but few details given — not clear if they used the same exact approach of that paper. A fresh paper on this effort is expected.
  44. Implementation of Variational Quantum Factoring algorithm by Stechly — GitHub repository for an implementation of the algorithm described in Variational Quantum Factoring by Anschuetz, Olson, Aspuru-Guzik, and Cao. This is unrelated to Shor’s algorithm — it’s an alternative approach.
  45. NSF/DOE Quantum Science Summer School presentation by Scott Pakin, June 8, 2017 — Two relevant slides. Still vague and incomplete, but does show some aspects well.
  46. O’Reilly Programming Quantum Computers: Essential Algorithms and Code Samples by Johnston, Harrigan, and Gimeno-Segovia — Book is not freely available online (other than “Look Inside” using Amazon), but code examples in GitHub are freely accessible online and can be run directly online, including implementation of Shor’s algorithm —
  47. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits by Craig Gidney and Martin Ekerå, 2019. I haven’t read it in enough detail to come to a judgment.
  48. Shor’s quantum factoring algorithm on a photonic chip, by Alberto Politi, Jonathan C. F. Matthews, and Jeremy L. O’Brien, 2009. “… an integrated waveguide silica-on-silicon chip that guides four single-photon qubits through the computation to factor 15.
  49. Realization of a scalable Shor algorithm by Thomas Monz, Daniel Nigg, Esteban A. Martinez, Matthias F. Brandl, Philipp Schindler, Richard Rines, Shannon X. Wang, Isaac L. Chuang, and Rainer Blatt, 2015. “… we report the realization of a fully scalable Shor algorithm as proposed by Kitaev. For this, we demonstrate factoring the number fifteen by effectively employing and controlling seven qubits and four “cache-qubits”, together with the implementation of generalized arithmetic operations, known as modular multipliers. The scalable algorithm has been realized with an ion-trap quantum computer exhibiting success probabilities in excess of 90%.
  50. Shor’s algorithm with fewer (pure) qubits by Christof Zalka, 2006. “In this note we consider optimised circuits for implementing Shor’s quantum factoring algorithm. First I give a circuit for which none of the about 2n qubits need to be initialised (though we still have to make the usual 2n measurements later on). Then I show how the modular additions in the algorithm can be carried out with a superposition of an arithmetic sequence. This makes parallelisation of Shor’s algorithm easier. Finally I show how one can factor with only about 1.5n qubits, and maybe even fewer.
  51. Efficient factorization with a single pure qubit and logN mixed qubits by S. Parker, M.B. Plenio, 2000/2005. “It is commonly assumed that Shor’s quantum algorithm for the efficient factorization of a large number N requires a pure initial state. Here we demonstrate that a single pure qubit together with a collection of log2N qubits in an arbitrary mixed state is sufficient to implement Shor’s factorization algorithm efficiently.
  52. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems by R.L. Rivest, A. Shamir, and L. Adleman — the original RSA, 1978.
  53. Improving the Success Probability for Shor’s Factoring Algorithm by Gregor Leander, 2002/2018. “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}.
  54. Factoring Safe Semiprimes with a Single Quantum Query by Frédéric Grosshans, Thomas Lawson, François Morain, Benjamin Smith, 2015/2016/2017. “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.
  55. Scaling laws for Shor’s algorithm with a banded quantum Fourier transform by Y. S. Nam, R. Blümel, 2013. “We investigate the performance of a streamlined version of Shor’s algorithm in which the quantum Fourier transform is replaced by a banded version that for each qubit retains only coupling to its b nearest neighbors. Defining the performance P(n,b) of the n-qubit algorithm for bandwidth b as the ratio of the success rates of Shor’s algorithm equipped with the banded and the full bandwidth (b=n−1) versions of the quantum Fourier transform, our numerical simulations show that P(n,b)≈exp[−φ2max(n,b)/100] for n<nt(b) (non-exponential regime) and P(n,b)≈2−ξb(n−8) for n>nt(b) (exponential regime), where nt(b), the location of the transition, is approximately given by nt(b)≈b+5.9+7.7(b+2)−47−−−−−−−−−−−−√ for b≳8, φmax(n,b)=2π[2−b−1(n−b−2)+2−n], and ξb≈1.1×2−2b. Analytically we obtain P(n,b)≈exp[−φ2max(n,b)/64] for n<nt(b) and P(n,b)≈2−ξ(a)bn for n>nt(b), where ξ(a)b≈π212ln(2)×2−2b≈1.19×2−2b. Thus, our analytical results predict the φ2max scaling (n<nt) and the 2−2b scaling (n>nt) of the data perfectly. In addition, in the large-n regime, the prefactor in ξ(a)b is close to the results of our numerical simulations and, in the low-n regime, the numerical scaling factor in our analytical result is within a factor 2 of its numerical value. As an example we show that b=8 is sufficient for factoring RSA-2048 with a 95% success rate.
  56. Approximate Quantum Fourier Transform with O(nlog(n)) T gates by Yunseong Nam, Yuan Su, Dmitri Maslov, 2018/2019. Reduces T-gate count from O(n log²(n)).


Generally, textbooks and other books have not been cited as references here since they tend not to be online (other than illegal, bootleg copies!) and free. I personally require online, free materials. But here is a brief list of books known to have relevant coverage of Shor’s algorithm:

  1. Quantum Computation and Quantum Information: 10th Anniversary Edition by Nielsen and Chuang — Popularly known as “Mike and Ike.”
  2. Quantum Computing: A Gentle Introduction by Rieffel and Polak —
  3. Quantum Computer Science: An Introduction by Mermin — Based on his lecture notes. Excerpt on Shor’s algorithm listed above in main references.
  4. O’Reilly Programming Quantum Computers: Essential Algorithms and Code Samples by Johnston, Harrigan, and Gimeno-Segovia — Code examples in GitHub are freely accessible online, including implementation of Shor’s algorithm which can be run directly online.
  5. Dancing with Qubits: How quantum computing works and how it can change the world by Sutor —

What’s next?

The lists in this paper will be updated as I become aware of additional references.

For more of my writing: List of My Papers on Quantum Computing.

Freelance Consultant