Shor's Factoring Algorithm: Lecture 16 of Quantum Computation at CMU

Shor's Factoring Algorithm: Lecture 16 of Quantum Computation at CMU

by Ryan O'Donnell

Formal & Physical Sciences Computing & Cybersecurity UYComputer scienceUYXNatural computing
🎙 Ryan O'Donnell 👥 14K 📅 November 2, 2018 ⏱ 80 min 👁 4K 📄 lecture 🧭 2026-08-17
Available in: English (current) Français

Keywords

Shor's algorithmquantum factoringorder-findingperiod-findingRSA

Summary

This lecture, part of a quantum computation course at CMU, focuses on Shor’s factoring algorithm. The instructor, Ryan O’Donnell, begins by reviewing the quantum period-finding algorithm from the previous lecture, which provides a clue to the period L of a function. He then outlines the two main parts of the lecture: first, how to use this clue to find L classically, and second, how order-finding reduces to factoring. The lecture emphasizes that the quantum part is already done, and the rest is classical number theory. The instructor explains the reduction from factoring to order-finding, showing that finding a non-trivial square root of 1 modulo B (the number to factor) yields a factor. He then describes a randomized algorithm to find such a square root using the order of a random element. The lecture covers the mathematical details, including the multiplicative group modulo B, the order of an element, and the periodicity of the function f(x) = a^x mod B. The instructor also discusses the efficiency of the algorithm, noting that it runs in polynomial time, and compares it to classical factoring algorithms. The lecture concludes with a brief mention of the historical context and the significance of Shor’s algorithm for cryptography.

201 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a clear and rigorous explanation of Shor’s algorithm, breaking it down into logical steps. The argumentation is solid, with mathematical proofs and derivations presented for key claims, such as the reduction from factoring to order-finding and the correctness of the period-finding approach. The instructor also addresses potential pitfalls and edge cases, such as the possibility of getting a multiple of the period, and explains how to handle them. The value of the information is high, as it offers a deep understanding of the algorithm’s inner workings, suitable for advanced students or researchers.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, with references to known results and prior homework problems. The instructor cites the work of Peter Shor and mentions the Miller-Rabin primality test and a master’s thesis by Heather Woll. The title accurately reflects the content, and the lecture is well-structured. The sources cited are appropriate and credible, though the lecture does not provide a formal bibliography. The content is consistent with established knowledge in quantum computing and number theory.

185 words

Title / Content Match

The title accurately describes the content: a lecture on Shor's factoring algorithm, part of a quantum computation course.

Quality & Reliability

9/10

Lecture by a CMU professor, part of a formal course, with clear mathematical derivations and references to known results. The content is rigorous and well-structured, though it is a lecture rather than peer-reviewed research.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

  • Course website — Course materials and lecture notes
  • Weekly work — Homework assignment related to the lecture
  • Panopto — Video recording platform
  • Diderot discussion board — Course discussion platform

Concurring Sources

Contribution & Novelties

This lecture provides a detailed and accessible explanation of Shor’s factoring algorithm, breaking it down into classical and quantum components. It clarifies the reduction from factoring to order-finding and the classical post-processing steps. The lecture is valuable for its pedagogical clarity and depth, making it a useful resource for students and researchers.

Pour aller plus loin :

85 words

Radar Profile

The radar profile shows high scores across all dimensions, indicating a well-balanced and comprehensive lecture. The high technical level and information quality are balanced by clear explanations, making it suitable for advanced audiences.

Reliability 9/10