How Quantum Computers Break Encryption | Shor's Algorithm Explained
Channel:minutephysics · Length:17:30 · Published:2019-05-01 · Views:3357229
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
- "Performance Matters" by Emery Berger · Strange Loop Conference · 42:15
- Why You Should Put YOUR MASK On First (My Brain Without Oxygen) - Smarter Every Day 157 · SmarterEveryDay · 10:17
- YouTubers have to declare ads. Why doesn't anyone else? · Tom Scott · 31:48
- Music Software & Interface Design: MuseScore · Tantacrul · 33:39
- Anagrams, but where you can break apart letters: "Anagraphs" · suckerpinch · 12:04
- Captain Disillusion: World's Greatest Blenderer - Live at the Blender Conference 2018 · Captain Disillusion · 41:43
- The man who faked human cloning · BobbyBroccoli · 1:04:45
- Music Software & Bad Interface Design: Avid’s Sibelius · Tantacrul · 21:35
- Quantum Computing for Computer Scientists · Microsoft Research · 1:28:22
- Behind the Scenes of iOS Security · Black Hat · 51:31
- Why Electronic Voting Is Still A Bad Idea · Tom Scott · 12:00
- But how does bitcoin actually work? · 3Blue1Brown · 25:15
- Diffie-Hellman Key Exchange · Art of the Problem · 8:38
- BlackHat USA 2011: SSL And The Future Of Authenticity · Christiaan008 · 48:01
- Blockchains Are a Bad Idea (James Mickens) · HBS Digital Initiative · 14:34
- Line Goes Up – The Problem With NFTs · Folding Ideas · 2:18:23