This note is part of [[quantum/Practical Quantum Information System]]. > [!info] Course code > Use the companion repository for this lecture's runnable lab, helper functions, and regression checks: > - [notebooks/by_concept/rsa_period_finding_and_shors_algorithm.ipynb](https://github.com/montekkundan/quantum-code/blob/main/notebooks/by_concept/rsa_period_finding_and_shors_algorithm.ipynb) > - [qcourse/algorithms.py](https://github.com/montekkundan/quantum-code/blob/main/qcourse/algorithms.py) > - [tests/test_expanded_course_primitives.py](https://github.com/montekkundan/quantum-code/blob/main/tests/test_expanded_course_primitives.py) [TODO: add video - RSA, Period Finding, and Shor's Algorithm] ## What This Concept Is Shor's algorithm is usually introduced as "the factoring algorithm that threatens RSA." That is true, but it hides the deeper structure. The real quantum core is [[quantum/Glossary#Period finding|period finding]]. RSA matters because factoring undermines it, so the cryptographic consequence makes the algorithm important to the wider world. The teaching challenge here is to keep the reduction chain visible. Factoring is not attacked head-on by a magic quantum subroutine. Instead, factoring is reduced to order finding, which is reduced to a periodicity problem, and the quantum part solves that periodicity structure efficiently. ## Foundation Terms You Need First [[quantum/Glossary#Period finding|Period finding]] is the core structured problem. [[quantum/Glossary#Quantum Fourier Transform|The Quantum Fourier Transform]] is the main circuit tool that makes the period visible. Classical number-theoretic post-processing is still required after the quantum part ends. Keep the hybrid nature of the algorithm in view: quantum subroutine in the middle, classical reduction and classical cleanup around it. ## How The Idea Actually Works RSA relies on the practical difficulty of factoring large composite integers. Shor's algorithm threatens that assumption by showing that if you can efficiently find the period of a modular arithmetic function, you can recover information that leads to the factors. The quantum subroutine does not simply output the factors. It creates a superposition over inputs, evaluates the periodic function coherently, and then uses Fourier structure to concentrate information about the period into measurement statistics. The observed output is then fed into a classical recovery step such as continued fractions. That means the algorithm is best understood in layers: 1. classical reduction from factoring to an order/period problem 2. quantum subroutine that makes the period accessible 3. classical post-processing that turns that period information into factors This layered understanding is essential because otherwise the algorithm feels like an opaque miracle. It is not a miracle. It is a carefully engineered interaction between algebra, Fourier analysis, and quantum coherence. ## Why It Matters - It is the most famous example of an exponential quantum speedup for a structured problem. - It links number theory, cryptography, Fourier methods, and circuit design. - It shows how serious quantum algorithms often combine classical and quantum work rather than replacing classical computation wholesale. ## Related Questions > [!question] What is the real quantum subroutine in Shor's algorithm? >> [!answer] Period finding. Factoring is reduced to order finding, and the quantum circuit is used to extract information about the period of a modular function. The factors come only after classical post-processing. > [!question] Why does Shor threaten RSA but not every cryptosystem equally? >> [!answer] RSA relies on the apparent classical hardness of factoring. Shor gives an efficient quantum algorithm for factoring. Other cryptosystems rely on different assumptions, so their quantum risk depends on whether those assumptions also admit quantum attacks. > [!question] Why is continued fractions part of a quantum algorithm note? >> [!answer] The quantum measurement gives a number related to a rational approximation of the hidden period. Continued fractions are the classical tool that recovers the candidate period from that sampled value. ## Additional Study Notes **Check yourself: the group size for $N=33$** Since $33=3\cdot11$, $\varphi(33)=33(1-1/3)(1-1/11)=20$. So $\mathbb{Z}_{33}^{\times}$ has 20 elements. **Check yourself: order of $2$ modulo $33$** The powers of $2$ modulo $33$ return to $1$ after 10 steps, so the order of $2$ in $\mathbb{Z}_{33}^{\times}$ is $10$. **Key fact: the standard gcd step can be unlucky** If the recovered order is even, Shor's classical post-processing checks $\gcd(x^{r/2}\pm1,N)$. For $N=33$, $x=2$, and $r=10$, $2^5\equiv-1\pmod{33}$, so this particular branch is the unlucky case for extracting nontrivial factors from $x^{r/2}\pm1$. **Check yourself: post-measurement first-register structure** If $Q=50$ and the period is $10$, then after measuring the function-value register, the first register can collapse to a uniform superposition over indices separated by $10$, such as $(|7\rangle+|17\rangle+|27\rangle+|37\rangle+|47\rangle)/\sqrt{5}$. **Check yourself: QFT peak spacing** With $Q=50$ and period $10$, Fourier samples concentrate on multiples of $Q/r=5$. The register size and the period together determine that spacing. **Question: Why do order finding and factoring need separate explanations?** The quantum subroutine estimates period/order information. Factoring is recovered by classical number theory after that. Keeping the two steps separate prevents the mistake of thinking the quantum circuit directly outputs the prime factors. ## Study Checks Use these after the explanation, not before it. ### Quick Checks - MCQ: What is the real quantum target in Shor's factoring algorithm? A. Sorting B. Period or order finding C. Linear regression D. Bell-state preparation **Answer:** B. Period or order finding. ### Oral Exam Anchors > [!question] Oral exam anchor > Explain why Shor's algorithm does not prove that NP-complete problems are easy for quantum computers. A good answer should say: Shor's algorithm gives a polynomial-time quantum algorithm for factoring and discrete logarithms. These problems have special algebraic structure, and the algorithm exploits period finding. NP-complete problems are not known to reduce to this same structure in a way that gives efficient quantum algorithms. Also, factoring is not known to be NP-complete. The existence of Shor's algorithm shows that some problems believed hard for classical computers are easy for quantum computers, but it does not imply BQP contains NP-complete problems. Grover's algorithm and black-box lower bounds are a warning against overgeneralizing quantum speedups. ## Practical Lab Break the work into a classical notebook and a quantum notebook so the reduction chain stays readable. - Build a tiny classical RSA example first. - Then implement a small order-finding or period-finding workflow and keep the classical post-processing separate from the quantum subroutine. - If available, add a resource-estimation or circuit-cost snapshot for the quantum part. ## Homework Emphasize that factoring is not the first quantum step in the chain. - Explain how factoring reduces to order finding or period finding. - Identify which parts of Shor's algorithm are classical and which are quantum. - Explain why this algorithm matters for RSA specifically. ## References - Scott Aaronson, [Introduction to Quantum Information Science](https://www.scottaaronson.com/qclec.pdf), Lectures 19 and 21. - [[Resources]] - IBM Quantum Learning, [learning portal](https://quantum.cloud.ibm.com/learning/en). - Microsoft Learn, [Azure Quantum documentation](https://learn.microsoft.com/en-us/azure/quantum/).