# 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.

- 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.
- 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.
- 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*. - I still have quite a few gaps in my comprehension of Shor’s algorithm, as detailed in my previously cited paper,
. 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.*Some Preliminary Questions About Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer* - Maybe to an expert in
*number theory*the gaps between the bits and pieces are*obvious*, but I’m no expert in number theory. - Actual
*implementations*of Shor’s algorithm are included as well, especially when a*GitHub repository*is used. *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.- Some
*alternatives*to Shor’s algorithm are also listed, although that was not a priority here. - 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. - I don’t have any coverage for the second part of Shor’s original paper, computing
*discrete logarithms*. - 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. - 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.
- 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:

. An approximation of a summary of Shor’s algorithm.*Ingredients for Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer*

# References

Now, the list of reference citations:

- Shor’s original paper —
— https://arxiv.org/abs/quant-ph/9508027.*Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer* - Wikipedia
article — https://en.wikipedia.org/wiki/Shor%27s_algorithm.*Shor’s algorithm* by Miller (1976) — https://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi76.pdf. Referenced by Shor’s original paper — “*Riemann’s Hypothesis and Tests for Primality**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.by Wolfram — https://reference.wolfram.com/language/ref/MultiplicativeOrder.html.*MultiplicativeOrder**Multiplicative order*is the more proper term for*order finding*, which is at the heart of Shor’s algorithm.- Scott Aaronson’s blog post —
— https://www.scottaaronson.com/blog/?p=208.*Shor, I’ll do it* - Wikipedia
article — https://en.wikipedia.org/wiki/Integer_factorization.*Integer factorization* - Wikipedia
article — https://en.wikipedia.org/wiki/Semiprime.*Semiprime* - Wolfram MathWorld definition of
— http://mathworld.wolfram.com/Semiprime.html.*Semiprime* — https://math.nist.gov/quantum/zoo/.*Quantum Algorithm Zoo*- Wikipedia
article — https://en.wikipedia.org/wiki/Chinese_remainder_theorem.*Chinese remainder theorem* - Wikipedia
article — https://en.wikipedia.org/wiki/Euler%27s_theorem.*Euler’s theorem* - Wikipedia
— https://en.wikipedia.org/wiki/Euler%27s_totient_function.*Euler’s totient function* by N. David Mermin — http://www.lassp.cornell.edu/mermin/factoring-princeton1.pdf.*What Has Quantum Mechanics to Do With Factoring? — Things I wish they had told me about Peter Shor’s algorithm*by Neal Young of Dartmouth — http://www.cs.ucr.edu/~neal/1996/cosc185-S96/shor/high-level.html.*The Quantum States of Shor’s Algorithm*by Lavor, Manssur, and Portugal — https://arxiv.org/abs/quant-ph/0303175.*Shor’s Algorithm for Factoring Large Integers*by Lomonaco — https://arxiv.org/abs/quant-ph/0010034.*Shor’s Quantum Factoring Algorithm*by Arora and Barak — http://theory.cs.princeton.edu/complexity/quantumchap.pdf.*Computational Complexity: A Modern Approach — Chapter 20 Quantum Computation*by Braunstein — https://www-users.cs.york.ac.uk/~schmuel/comp/comp.html.*Quantum computation: a tutorial*paper by Beauregard — https://arxiv.org/abs/quant-ph/0205095. One of the derivative algorithms.*Circuit for Shor’s algorithm using 2n+3 qubits*paper by Pavlidis and Gizopoulos — https://arxiv.org/abs/1207.0511. Requires 9n + 3 qubits, but fewer gate executions. Another derivative algorithm.*Fast Quantum Modular Exponentiation Architecture for Shor’s Factorization Algorithm*paper by Dattani and Bryans — https://arxiv.org/abs/1411.6758. An alternative algorithm.*Quantum factorization of 56153 with only 4 qubits*— http://blendmaster.github.io/ShorJS/. “*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.— https://inst.eecs.berkeley.edu/~cs191/fa05/lectures/lecture19_fa05.pdf.*Shor’s order (period) finding algorithm and factoring — C/CS/Phys 191 11/01/05 — Fall 2005 Lecture 19 notes*paper by Lavor, Manssur, and Portugal — https://arxiv.org/abs/quant-ph/0303175. “*Shor’s Algorithm for Factoring Large Integers**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.*”paper by Grosshans, Lawson, Morain, and Smith — https://arxiv.org/abs/1511.04385. “*Factoring Safe Semiprimes with a Single Quantum Query**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.- Alas, I am unable to give the
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.*Quantum Computation and Quantum Information* - IBM Q Experience documentation —
— https://quantumexperience.ng.bluemix.net/proxy/tutorial/full-user-guide/004-Quantum_Algorithms/110-Shor's_algorithm.html.*Shor’s algorithm* - NIST Post-Quantum Cryptography effort — https://csrc.nist.gov/projects/post-quantum-cryptography.
- Wikipedia
article — https://en.wikipedia.org/wiki/Post-quantum_cryptography.*Post-quantum cryptography* paper by Wang, Jiang, Mu, and Fan — https://arxiv.org/abs/1707.06430.*A quantum algorithm for greatest common divisor problem*— https://qudev.phys.ethz.ch/content/QSIT15/Shors%20Algorithm.pdf.*Shor’s Algorithm presentation by Bäumer, Sobez, and Tessarini*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.*Shor’s Algorithm and the 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*Scaling laws for Shor’s algorithm with a banded quantum Fourier transform**banded*QFT for much better performance.by Nam and Blümel — https://arxiv.org/abs/1601.07497. Yet another adaptation of Shor’s algorithm to boost performance.*Symmetry boosts quantum computer performance*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.*Quantum Computing Lecture Notes*lecture notes by Dave Bacon, Department of Computer Science & Engineering, University of Washington — https://courses.cs.washington.edu/courses/cse599d/06wi/lecturenotes11.pdf.*CSE 599d — Quantum Computing — Shor’s Algorithm*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.*Experimental Realization of an Order-Finding Algorithm with an NMR Quantum Computer*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.*Quantum Algorithm Implementations for Beginners*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.*A Re-evaluation of Shor’s Algorithm*by Alec Brickner — https://cs269q.stanford.edu/projects2019/Brickner_Y.pdf. Student project for*Shor’s Algorithm in Pyquil*course at Stanford.*CS 269Q: Quantum Computer Programming*by William Burton — https://cs269q.stanford.edu/projects2019/burton_Y.pdf. Student project for*Implementation of Shor’s algorithm in pyQuil*course at Stanford.*CS 269Q: Quantum Computer Programming*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.*Realization of a scalable Shor algorithm*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.*Variational Quantum Factoring*by Stechly — https://github.com/mstechly/vqf. GitHub repository for an implementation of the algorithm described in*Implementation of Variational Quantum Factoring algorithm*by Anschuetz, Olson, Aspuru-Guzik, and Cao. This is unrelated to Shor’s algorithm — it’s an alternative approach.*Variational Quantum Factoring*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.*NSF/DOE Quantum Science Summer School*- O’Reilly
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/.*Programming Quantum Computers: Essential Algorithms and Code Samples* by Craig Gidney and Martin Ekerå, 2019. I haven’t read it in enough detail to come to a judgment.*How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits*, by Alberto Politi, Jonathan C. F. Matthews, and Jeremy L. O’Brien, 2009. “…*Shor’s quantum factoring algorithm on a photonic chip**an integrated waveguide silica-on-silicon chip that guides four single-photon qubits through the computation to factor 15.*”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. “…*Realization of a scalable Shor algorithm**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%.*”by Christof Zalka, 2006. “*Shor’s algorithm with fewer (pure) qubits**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.*”by S. Parker, M.B. Plenio, 2000/2005. “*Efficient factorization with a single pure qubit and logN mixed qubits**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.*”by R.L. Rivest, A. Shamir, and L. Adleman — the original RSA, 1978.*A Method for Obtaining Digital Signatures and Public-Key Cryptosystems*

https://people.csail.mit.edu/rivest/Rsapaper.pdf

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.5588- 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}.*” by Frédéric Grosshans, Thomas Lawson, François Morain, Benjamin Smith, 2015/2016/2017. “*Factoring Safe Semiprimes with a Single Quantum Query**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.*”by Y. S. Nam, R. Blümel, 2013. “*Scaling laws for Shor’s algorithm with a banded quantum Fourier transform**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.*”by Yunseong Nam, Yuan Su, Dmitri Maslov, 2018/2019. Reduces T-gate count from O(n log²(n)).*Approximate Quantum Fourier Transform with O(nlog(n)) T gates*

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

by Nielsen and Chuang — https://www.amazon.com/Quantum-Computation-Information-10th-Anniversary/dp/1107002176. Popularly known as “Mike and Ike.”*Quantum Computation and Quantum Information: 10th Anniversary Edition*by Rieffel and Polak — https://www.amazon.com/Quantum-Computing-Introduction-Engineering-Computation/dp/0262015064.*Quantum Computing: A Gentle 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.*Quantum Computer Science: An Introduction*- O’Reilly
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.*Programming Quantum Computers: Essential Algorithms and Code Samples* by Sutor — https://www.amazon.com/Dancing-Qubits-quantum-computing-change/dp/1838827366.*Dancing with Qubits: How quantum computing works and how it can change the world*

# 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**.