# 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*. 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.*Beware of Quantum Algorithms Dependent on Fine Granularity of Phase*Not focused on Shor’s algorithm, but relevant, and there is a section,*Is Lack of Fine Granularity of Phase and Probability Amplitude the Fatal Achilles Heel Which Dooms Quantum Computing to Severely Limited Utility?**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:

- 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*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 “*Factoring integers with sublinear resources on a superconducting quantum processor**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.

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