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.
3. Beware of Quantum Algorithms Dependent on Fine Granularity of Phase. Algorithms such as Shor’s factoring algorithm utilize quantum Fourier transform (QFT) which in turn relies on very fine granularity of phase, which is likely to be problematic for factoring of very large semiprime numbers, such as large public encryption keys — including 1024, 2048, and 4096 bits. Whether these issues can be successfully mitigated is unknown.
4. Is Lack of Fine Granularity of Phase and Probability Amplitude the Fatal Achilles Heel Which Dooms Quantum Computing to Severely Limited Utility? Not focused on Shor’s algorithm, but relevant, and there is a section, What about Shor’s factoring algorithm? Sorry, but it will only work for small numbers, not very large numbers.

References

Now, the list of reference citations:

1. Shor’s original paper — Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer — https://arxiv.org/abs/quant-ph/9508027.
2. Wikipedia Shor’s algorithm article — https://en.wikipedia.org/wiki/Shor%27s_algorithm.
3. Riemann’s Hypothesis and Tests for Primality by Miller (1976) — https://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi76.pdf. 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 — https://reference.wolfram.com/language/ref/MultiplicativeOrder.html. 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 — https://www.scottaaronson.com/blog/?p=208.
6. Wikipedia Integer factorization article — https://en.wikipedia.org/wiki/Integer_factorization.
7. Wikipedia Semiprime article — https://en.wikipedia.org/wiki/Semiprime.
8. Wolfram MathWorld definition of Semiprime — http://mathworld.wolfram.com/Semiprime.html.
9. Quantum Algorithm Zoo — https://math.nist.gov/quantum/zoo/.
10. Wikipedia Chinese remainder theorem article — https://en.wikipedia.org/wiki/Chinese_remainder_theorem.
11. Wikipedia Euler’s theorem article — https://en.wikipedia.org/wiki/Euler%27s_theorem.
12. Wikipedia Euler’s totient function — https://en.wikipedia.org/wiki/Euler%27s_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 — http://www.lassp.cornell.edu/mermin/factoring-princeton1.pdf.
14. The Quantum States of Shor’s Algorithm by Neal Young of Dartmouth — http://www.cs.ucr.edu/~neal/1996/cosc185-S96/shor/high-level.html.
15. Shor’s Algorithm for Factoring Large Integers by Lavor, Manssur, and Portugal — https://arxiv.org/abs/quant-ph/0303175.
16. Shor’s Quantum Factoring Algorithm by Lomonaco — https://arxiv.org/abs/quant-ph/0010034.
17. Computational Complexity: A Modern Approach — Chapter 20 Quantum Computation by Arora and Barak — http://theory.cs.princeton.edu/complexity/quantumchap.pdf.
18. Quantum computation: a tutorial by Braunstein — https://www-users.cs.york.ac.uk/~schmuel/comp/comp.html.
19. Circuit for Shor’s algorithm using 2n+3 qubits paper by Beauregard — https://arxiv.org/abs/quant-ph/0205095. One of the derivative algorithms.
20. Fast Quantum Modular Exponentiation Architecture for Shor’s Factorization Algorithm paper by Pavlidis and Gizopoulos — https://arxiv.org/abs/1207.0511. 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 — https://arxiv.org/abs/1411.6758. An alternative algorithm.
22. Shor’s Algorithm Simulator — http://blendmaster.github.io/ShorJS/. “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 — https://inst.eecs.berkeley.edu/~cs191/fa05/lectures/lecture19_fa05.pdf.
24. Shor’s Algorithm for Factoring Large Integers paper by Lavor, Manssur, and Portugal — https://arxiv.org/abs/quant-ph/0303175. “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 — https://arxiv.org/abs/1511.04385. “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 http://www.michaelnielsen.org/qcqi/ and https://www.amazon.com/Quantum-Computation-Information-10th-Anniversary/dp/1107002176.
27. IBM Q Experience documentation — Shor’s algorithm — https://quantumexperience.ng.bluemix.net/proxy/tutorial/full-user-guide/004-Quantum_Algorithms/110-Shor's_algorithm.html.
28. NIST Post-Quantum Cryptography effort — https://csrc.nist.gov/projects/post-quantum-cryptography.
29. Wikipedia Post-quantum cryptography article — https://en.wikipedia.org/wiki/Post-quantum_cryptography.
30. A quantum algorithm for greatest common divisor problem paper by Wang, Jiang, Mu, and Fan — https://arxiv.org/abs/1707.06430.
31. Shor’s Algorithm presentation by Bäumer, Sobez, and Tessarini — https://qudev.phys.ethz.ch/content/QSIT15/Shors%20Algorithm.pdf.
32. Shor’s Algorithm and the Quantum Fourier Transform by Fang Xi Lin of McGill University — http://www.math.mcgill.ca/darmon/courses/12-13/nt/projects/Fangxi-Lin.pdf. 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 — https://arxiv.org/abs/1302.5844. 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 — https://arxiv.org/abs/1601.07497. Yet another adaptation of Shor’s algorithm to boost performance.
35. Quantum Computing Lecture Notes by Mark Oskin of University of Washington — https://homes.cs.washington.edu/~oskin/quantum-notes.pdf. 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 — https://courses.cs.washington.edu/courses/cse599d/06wi/lecturenotes11.pdf.
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 — https://arxiv.org/abs/quant-ph/0007017. 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 — https://arxiv.org/abs/1804.03719. 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 — https://arxiv.org/pdf/quant-ph/0612077. 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 — https://cs269q.stanford.edu/projects2019/Brickner_Y.pdf. Student project for CS 269Q: Quantum Computer Programming course at Stanford.
41. Implementation of Shor’s algorithm in pyQuil by William Burton — https://cs269q.stanford.edu/projects2019/burton_Y.pdf. 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 — https://science.sciencemag.org/content/351/6277/1068. 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 — https://arxiv.org/abs/1808.08927. 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 — https://github.com/mstechly/vqf. 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 — http://qs3.mit.edu/images/pdf/QS3-2017---Pakin-Lecture.pdf. 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 — https://www.amazon.com/Programming-Quantum-Computers-Essential-Algorithms/dp/1492039683. 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 — https://oreilly-qc.github.io/.
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.
    https://people.csail.mit.edu/rivest/Rsapaper.pdf
    http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.5588
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)).
57. Factoring integers with sublinear resources on a superconducting quantum processor by Bao Yan, Ziqi Tan, Shijie Wei, et al, 2022. Caused quite an uproar. Dubious whether it really would scale from 48 bits to 2048 or 40096 bits even if it could factor a 48-bit semiprime using only 10 qubits. Not really directly relevant to Shor’s algorithm per se, but would supplant Shor’s algorithm if it indeed worked for semiprimes of substantial size. The authors claim “We find that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 even in the simplest 1D-chain system. Such a scale of quantum resources is most likely to be achieved on NISQ devices in the near future”, but it simply isn’t credible that the algorithm could achieve such results “on NISQ devices in the near future.” They also claim “The quantum circuit depth of QAOA with single layer is 1118 in Kn topology system, 1139 in 2DSL system and 1490 in the simplest LNN system, which is achievable for the NISQ devices in the near future or even today”, but once again this simply isn’t credible that the algorithm could achieve such results “for the NISQ devices in the near future or even today.” Computer security expert Bruce Schneier shockingly posted that “Honestly, most of the paper is over my head…” Wow… if even security super-expert Bruce Schneier can’t understand this paper in gruesome detail, that speaks volumes for how out of control encryption — and quantum computing — have gotten. Granted, I don’t understand every detail of the paper either, but I can grasp enough to sense that it has holes and gaps and potential issues. For example, variational methods such as QAOA can be problematic at best and dubious with respect to scaling. And even if it works fine for relatively small keys such as 48 bits, dependence on fine granularity of phase or probability amplitude make scaling to much larger keys a virtual slam-dunk to fail for keys much bigger than 48 bits. Sure, maybe it might work for 64 or 80 or 96 bits, but expecting it to scale for fine rotations needed for 2048 or 4096 is a definite no-go. Huh… they didn’t even mention scaling from 2048 to 4096 or larger. But maybe the bottom line point for this paper is that it raises far more questions than it answers. Or maybe that’s a feature not a bug — maybe it was intended to be a teaser rather than a complete approach.
58. Large-Scale Simulation of Shor’s Quantum Factoring Algorithm by Dennis Willsch, Madita Willsch, Fengping Jin, Hans De Raedt, and Kristel Michielsen, 2023. “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 549755813701 = 712321 * 771781. We put forward the challenge of factoring, without oversimplification, a non-trivial semiprime larger than this number on any quantum computing device.”

Books

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 — https://www.amazon.com/Quantum-Computation-Information-10th-Anniversary/dp/1107002176. Popularly known as “Mike and Ike.”
2. Quantum Computing: A Gentle Introduction by Rieffel and Polak — https://www.amazon.com/Quantum-Computing-Introduction-Engineering-Computation/dp/0262015064.
3. Quantum Computer Science: An Introduction by Mermin — https://www.amazon.com/Quantum-Computer-Science-David-Mermin/dp/0521876583. 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 — https://www.amazon.com/Programming-Quantum-Computers-Essential-Algorithms/dp/1492039683. 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 — https://www.amazon.com/Dancing-Qubits-quantum-computing-change/dp/1838827366.

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.