How Quantum Computers Break Encryption | Shors Algorithm Explained @MinutePhysics
How Quantum Computers Break Encryption | Shors Algorithm Explained  @MinutePhysics
Uploaded May 2019 | Updated November 2026, 4 days ago
Go to dashlane.com/minutephysics to download Dashlane for free, and use offer code minutephysics for 10% off Dashlane Premium!

Support MinutePhysics on Patreon! patreon.com/minutephysics

This video explains Shor’s Algorithm, a way to efficiently factor large pseudoprime integers into their prime factors using a quantum computer. The quantum computation relies on the number-theoretic analysis of the factoring problem via modular arithmetic mod N (where N is the number to be factored), and finding the order or period of a random coprime number mod N. The exponential speedup comes in part from the use of the quantum fast fourier transform which achieves interference among frequencies that are not related to the period (period-finding is the goal of the QFT FFT).

REFERENCES

RSA Numbers (sample large numbers to try factoring)
en.wikipedia.org/wiki/RSA_numbers

IBM on RSA
ibm.com/support/knowledgecenter/en/SSB23S1.1.0.13/gtps7/s7pkey.html

Modulo Multiplication Group Tables
mathworld.wolfram.com/ModuloMultiplicationGroup.html

Difference of squares factorization
en.wikipedia.org/wiki/Difference_of_two_squares

Euclid’s Algorithm
en.wikipedia.org/wiki/Euclideanalgorithm

Rational sieve for factoring
en.wikipedia.org/wiki/Rational_sieve

General Number field Sieve
en.wikipedia.org/wiki/Generalnumberfieldsieve

Scott Aaronson blog post about Shor’s Algorithm
scottaaronson.com/blog/?p=208

Experimental implementation of Shor’s Algorithm (factoring 15, 21, and 35)
arxiv.org/pdf/1903.00768.pdf

Adiabatic Quantum Computation factoring the number 291311
arxiv.org/pdf/1706.08061.pdf

Scott Aaronson course notes
scottaaronson.com/qclec
scottaaronson.com/qclec/combined.pdf

Shor’s Algorithm on Quantiki
quantiki.org/wiki/shors-factoring-algorithm

TLS And SSL use RSA encryption
en.wikipedia.org/wiki/TransportLayerSecurity

Dashlane security whitepaper
dashlane.com/download/DashlaneSecurityWhitePaperOctober2018.pdf


Link to Patreon Supporters: minutephysics.com/supporters

MinutePhysics is on twitter - @minutephysics

And facebook - facebook.com/minutephysics

Minute Physics provides an energetic and entertaining view of old and new problems in physics -- all in a minute!

Created by Henry Reich
How Quantum Computers Break Encryption | Shors Algorithm ExplainedThe Color Temperature ParadoxWhy December Has The Longest DaysHow Modern Light Bulbs WorkWhat Is The Shape of Space? (ft. PhD Comics)I Had to Build a Custom Mute Switch for my ViolinHow Do Bikes Stay Up?The No Cloning TheoremProtecting Privacy with MATH (Collab with the Census)Why Do Wind Turbines Have Three Blades?Footnote †: Unstable EquilibriumWhat is the farthest on earth you can get from ANYTHING
minutephysics |

How Quantum Computers Break Encryption | Shor's Algorithm Explained

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER