How Quantum Computers Break Encryption | Shor's Algorithm Explained

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)

IBM on RSA

Modulo Multiplication Group Tables

Difference of squares factorization

Euclid’s Algorithm

Rational sieve for factoring

General Number field Sieve

Scott Aaronson blog post about Shor’s Algorithm

Experimental implementation of Shor’s Algorithm (factoring 15, 21, and 35)

Adiabatic Quantum Computation factoring the number 291311

Scott Aaronson course notes

Shor’s Algorithm on Quantiki

TLS And SSL use RSA encryption

Dashlane security whitepaper

MinutePhysics is on twitter - @minutephysics

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

Created by Henry Reich

[ghufranullah]

Hey, that's a lot of minutes of physics.

[gabriel]

My brain waves superpositioned in a way that only the neurons which did not undertand got positive interference

[bluesy]

Him: "...and here's the clever part."
Me: "WHAT WAS THE REST OF THIS?!"

[brenorocha]

It's amazing to see that someone can grasp such difficult concepts well enough to make this "simple" explanation. I don't have the knowledge to understand, but I still can have an idea of what it's about. And it's even more reassuring to see comments from physics students who find this video useful in addition to their study material. Thank you very much and keep the good work!

[cannaroe]

Me at the half mark: "This couldn't get anymore complicated."
minutephysics: *_"Fourier Transforms!"_*

[WAMTAT]

I think I follow. Smart computer makes maths go fast. Fast math is equal to no more computer security.

[miamesa]

*I HAVE UNDERSTOOD. NOTHING. AT. ALL.*

[jcolinmizia]

The scary part of this is that breaking encryption is no longer a mathematical or scientific question, it’s an engineering question.

[idndyzgaming]

"I'm going to attempt to explain"


*me: brain explodes*

[henrygao]

As a physics student I clicked into this thinking it's just another super basic introductory video...

Ends up thoroughly reviewing 2 weeks of solid materials from my quantum computing class

Edit: Highly recommend a quantum computing class if you can take one! More of a math class than physics but still super interesting

[jellovendigar]

I love how he makes very hard concepts approachable. Now I’ll share this video with anyone who thinks quantum computers are basically magic

[tauhidzaman]

Thanks for making this video. I took a class with Peter Shor and I still didnt understand his algorithm. But this video makes it so clear. Great work!

[Asocialite__]

0:59 With you so far
1:02 Shor's Algorithm... never heard of it but I can dig it
3:57 Ok... just explain what Shor's Algorithm is...
7:31 Uhh....
8:56 Ok wait, stop
11:52 Ok man, you just keep talking, I'm gonna go write a comment

[davidmelendezsoto]

I watch this when I’m feeling too smart
To remind myself that I’m not really smart

[splodeyferret]

Incredible and impressive that a whole video on breaking industry standard encryption with quantum computers doesn't mention prime numbers... it's like you figured that it was an extra complication that didn't need to be there for the purposes of this video, and you're right!

[comoli]

I did a project on shors algorithms problems and benefits, instead of trying to explain what it did, I just summed it up with "using math" 😂.

[theCodyReeder]

Why do I get the feeling we're about to break the game?

[DanDan-yybo]

I‘m gonna be honest, at a certain point I didn’t understand it anymore, but just the fact that I understood half of it is good enough and it just shows how good you explain things. Great channel, keep it up!

[commanderzander]

This can be used against asymmetric encryption, but not symmetric encryption, which is what most data uses. Symmetric encryption takes a random string of letters and numbers, and uses that string to mash up the data in specific ways that you can't undo without knowing what the string is. No factoring is involved, and you can't use Shor's algorithm. However, getting your secret string to someone you trust usually DOES include asymmetric encryption. But if the quantum attacker missed the key exchange, you can't break in by doing this.

[kenedi]

Great vid, thanks minutephysics! Been following your channel since I was 9 or 10 and now I'm going into uni and your content is still great and useful.