u/igmrlmin r/compsci • Recommends
How quantum computers break encryption - - Shor's algorithm explained
0:00 / 0:00
#shor'salgorithm#quantumcomputing#rsa
How Quantum Computers Break Encryption | Shor's Algorithm Explained
minutephysics
5.9M subscribers • 5 videos on Hallway
- Recommended by 5 people: 3 on Hacker News and 2 in engineering communities.
- A classic. People kept recommending it from 2019 to 2023.
- Linked in the descriptionarXiv 1903.00768arXiv 1706.08061
Intermediate. Assumes working knowledge.
3.3M views7 years ago5 recommendations
Computer scienceSecurityQuantum computingCryptographyAlgorithms
How quantum computers can factor large integers and break encryption using Shor's algorithm.
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/s7pk… 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.… 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 ReichWhy it's here
5 people recommend thisWhat people say. Recommended as a clear explanation of Shor's algorithm and how quantum computers achieve exponential speedup over classical factoring.
glandiumon Hacker News • Recommends
On “Quantum supremacy: the gloves are off”
Minute Physics has a really good explanation of Shor's algorithm, and by proxy, Quantum computing. link to this video And the followup: link
xmprton Hacker News • Recommends
On “What makes quantum computing so hard to explain?”
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. link to this video
diginovaon Hacker News • Recommends
On “Quantum Computing 101”
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 link to this video
u/bbno3in r/compsci • Recommends
How Quantum Computers Break Encryption | Shor's Algorithm Explained
u/igmrlmin r/compsci • Recommends
How quantum computers destroy Internet Security: Shor's algorithm explained
u/igmrlmin r/compsci • Recommends
How quantum computers break encryption: Shor's algorithm explained
u/PiLord314in r/compsci • Mentions
On “What's the difference between a ternary computer and a quantum computer?”
At least as far as I understand for the proposed algorithm that breaks SHA-256 and other prime based encryption^(1): basically the part of quantum computers that is interesting isn't that they can hold an additional bit^(2) but that the q-bits have destructive interference in between each other which allows you to search over a larger space on each algorithmic iteration.
1 - Video that explains Shor's algorithm: [video
2 - As others have pointed out there are not three states, it's that the q-bits have relative phase to each other. When the phase is not 0 or 180 you get a "superposition" of being both 1 and 0 with probability depending on the angle.