Login / Register

How Quantum Computers Break Encryption | Shor's Algorithm Explained

Thanks! Share it with your friends!


You disliked this video. Thanks for the feedback!

Sorry, only registred users can create playlists.

Channel: minutephysics
Categories: Computer Science   |   Physics   |   Science   |   Technology  
 Find Related Videos  added


Go to to download Dashlane for free, and use offer code minutephysics for 10% off Dashlane Premium!

Support MinutePhysics on Patreon!

This video explains Shors 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).


RSA Numbers (sample large numbers to try factoring)


Modulo Multiplication Group Tables

Difference of squares factorization

Euclids Algorithm

Rational sieve for factoring

General Number field Sieve

Scott Aaronson blog post about Shors Algorithm

Experimental implementation of Shors Algorithm (factoring 15, 21, and 35)

Adiabatic Quantum Computation factoring the number 291311

Scott Aaronson course notes

Shors Algorithm on Quantiki

TLS And SSL use RSA encryption

Dashlane security whitepaper

Link to Patreon Supporters:

MinutePhysics is on twitter - @minutephysics

And facebook -

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

Created by Henry Reich

Post your comment


Be the first to comment