How Quantum Computers Break Encryption | Shor's Algorithm Explained

Channel:minutephysics · Length:17:30 · Published:2019-05-01 · Views:3357229

Watch on YouTube

Summary

MinutePhysics explains Shor's algorithm, showing how a quantum computer factors large integers by finding the period of a number modulo N. It walks through the modular arithmetic and number theory that give the exponential speedup over classical factoring, and why this threatens encryption.

Why HN recommends it

HN commenters point to it as a clear, approachable explanation of Shor's algorithm and what quantum computers actually do.

Minute Physics has a really good explanation of Shor's algorithm, and by proxy, Quantum computing. — HN, 2019

Cryptography · Quantum computing

Subtitles (excerpt)

The goal of encryption is to garble data is such a way so that no one who has the data can read it unless they’re the intended recipient. And the encryption of pretty much all private information sent over the internet relies immensely on one numerical phenomenon - as far as we can tell, it’s really really hard to take a really big number and find its factors using a normal, non-quantum computer. Unlike multiplication, which is very fast (just multiply the digits together and add them up ), finding the prime numbers that multiply together to give you an arbitrary, big, non-prime number appears to be slow - at least, the best approach we currently have that runs on a normal computer - even a very powerful one - is very slow. Like, to find the factors of this number , it took 2000 years of computer processor time! Now, it’s not yet proven that we won’t eventually find a fast way to break encryption just with normal computers, but it’s certain that anybody with a large working quantum computer today would pose an immediate privacy and security threat to the whole internet. And that’s due to something called “Shor’s Algorithm.” Well actually it’s due to quantum superposition and interference; they’re just taken advantage

On Hacker News

This video clears a most important misconception everyone has regarding QC which is "How a QC does operation's parallelly and what does that even mean when you can only get 1 output irl?" I hope I myself have understood it correctly if that's right Also Minute Physics video for the Shor's Algorithm is good explaination [VIDEO] — diginova, 2023-04
This helped me a lot and I think it made the rounds on hackernews a while back as well. [LINK] There's also this video which walks through how quantum computers solve a very specific factoring problem (Shor's Algorithm) in a way that classical computers cannot. [VIDEO] — xmprt, 2021-06
Minute Physics has a really good explanation of Shor's algorithm, and by proxy, Quantum computing. [VIDEO] And the followup: [LINK] — glandium, 2019-10

Related videos