How Quantum Computers Break Encryption | Shor's Algorithm Explained

How Quantum Computers Break Encryption | Shor's Algorithm Explained

Go to http://www.dashlane.com/minutephysics to download Dashlane for free, and use offer code minutephysics for 10% off Dashlane Premium!

Support MinutePhysics on Patreon! http://www.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)
https://en.wikipedia.org/wiki/RSA_numbers

IBM on RSA
https://www.ibm.com/support/knowledgecenter/en/SSB23S1.1.0.13/gtps7/s7pkey.html

Modulo Multiplication Group Tables
http://mathworld.wolfram.com/ModuloMultiplicationGroup.html

Difference of squares factorization
https://en.wikipedia.org/wiki/Difference_of_two_squares

Euclid’s Algorithm
https://en.wikipedia.org/wiki/Euclideanalgorithm

Rational sieve for factoring
https://en.wikipedia.org/wiki/Rational_sieve

General Number field Sieve
https://en.wikipedia.org/wiki/Generalnumberfieldsieve

Scott Aaronson blog post about Shor’s Algorithm

Shor, I’ll do it

Experimental implementation of Shor’s Algorithm (factoring 15, 21, and 35)
https://arxiv.org/pdf/1903.00768.pdf

Adiabatic Quantum Computation factoring the number 291311
https://arxiv.org/pdf/1706.08061.pdf

Scott Aaronson course notes
https://www.scottaaronson.com/qclec/
https://www.scottaaronson.com/qclec/combined.pdf

Shor’s Algorithm on Quantiki
https://www.quantiki.org/wiki/shors-factoring-algorithm

TLS And SSL use RSA encryption
https://en.wikipedia.org/wiki/TransportLayerSecurity

Dashlane security whitepaper
https://www.dashlane.com/download/DashlaneSecurityWhitePaperOctober2018.pdf

Link to Patreon Supporters: http://www.minutephysics.com/supporters/

MinutePhysics is on twitter – @minutephysics

And facebook – http://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 Reich

50 Comments

  1. warmCabin on November 13, 2019 at 6:13 pm

    Dashlane’s cool and all, but it doesn’t sound like it’s Shor-proof.



  2. Insert your feelings [here] on November 13, 2019 at 6:15 pm

    Video wasn’t a minute dislike for misleading channel name



  3. Jordan Crawford on November 13, 2019 at 6:16 pm

    I was so focused until the baseline came in and said, “just give it up, dude.”



  4. Gabriel2005_11 / gaming on November 13, 2019 at 6:16 pm

    top 10 facts that will have almost no difference in your life



  5. Aysha's Kitchen on November 13, 2019 at 6:16 pm

    Wow alot of math



  6. Shahid Nehal on November 13, 2019 at 6:16 pm

    Looked outside the window for 15 secs, got back to the video and I was lost 🙁



  7. GrossZastrow on November 13, 2019 at 6:17 pm

    Hooking up time crystals with quantum computers will enable the cracking of any encryption used today. I’m pretty damned sure people are working on this…. and some of them are not very nice.



  8. PlasmaRuler on November 13, 2019 at 6:17 pm

    It’s not that bad but if you don’t have 2 factor authentication yeah your screwed



  9. Snubagaff on November 13, 2019 at 6:17 pm

    Head hurty



  10. Spencer Shackleton on November 13, 2019 at 6:19 pm

    what



  11. Jordan Hicks on November 13, 2019 at 6:21 pm

    all i learned is how we encrypt stuff
    was gonna say how but i cant explain it 😛



  12. Shaunak Marathe on November 13, 2019 at 6:21 pm

    That’s the Fermat’s Little theorem @ 5:19



  13. Dota2 Lesson on November 13, 2019 at 6:22 pm

    i loved the video, well done. still you got a thump down for the ad at the end + no subscription



  14. Jake Jelinek on November 13, 2019 at 6:22 pm

    But can quantuim computer decode girls "hints"?



  15. faox on November 13, 2019 at 6:28 pm

    I was thinking about this when I heard the news about Google’s “breakthrough”. They read my mind



  16. Marv3Lthe1 on November 13, 2019 at 6:29 pm

    In Quantum world, you could be a man, a woman and a ladyboy at the same time.



  17. YtoSk on November 13, 2019 at 6:34 pm

    i understand almost everything. the only thing i don’t is how you do that smooth transition between quantum mechanics and advertising your sponsor. you are a genius.



  18. Kyle Chin on November 13, 2019 at 6:34 pm

    Watch as I destroy the world’s economy by turning a 1 into a 0.



  19. NCR Trooper on November 13, 2019 at 6:34 pm

    And then alter the website code a bit to add a captcha



  20. ngocbach phan on November 13, 2019 at 6:36 pm

    Why can’t we just take a perfect number for g? That way, even if p is odd, g^p/2+1 or g^p/2-1 will still be a natural number.



  21. therealquade on November 13, 2019 at 6:36 pm

    So uhhhhh about Google’s quantum computer….



  22. Yellow Diamond on November 13, 2019 at 6:37 pm

    why dont u jsut put 1, isn’t that a factor of every whole number?



  23. mhe0815 on November 13, 2019 at 6:38 pm

    Thank you. After watching this, I feel smarter and dumber at the same time now.



  24. Retro Lad on November 13, 2019 at 6:39 pm

    13:58 ‘I’m oversimplifying a bit here’
    Lol what



  25. Retro Lad on November 13, 2019 at 6:39 pm

    Why am I watching this and how did I get here



  26. shad sluiter on November 13, 2019 at 6:42 pm

    Perfect. Shor’s algorithm should be mentioned with all of the news stories that are currently covering Google’s claim to have created a working quantum computer.



  27. the1gip on November 13, 2019 at 6:44 pm

    4:47 So in the case of recurring decimals, this would be true of say A=10, B=7, P=6, m=142857 then?



  28. GraphicGore on November 13, 2019 at 6:44 pm

    Shor Algorithm: will break all encryption, none of your data is safe
    Quantum cryptography: i am about to ruin this man day



  29. The Legend of Tobi on November 13, 2019 at 6:46 pm

    Great explanation! Thank you 🙂



  30. Tes Tos on November 13, 2019 at 6:47 pm

    Anyone has Aspiring? Bottom line is nothing is secure and now less than ever. Keep your money under the mattress and an AR next to your bed. Better yet put a sign by the front door telling everyone where is your cash and just let them in and take it, if you shoot a thieve most likely you will need that cash to get you out of jail either way your going to loose everything thanks to your government.



  31. Kyle Chin on November 13, 2019 at 6:50 pm

    But remember people no need to panic because this only works for numerical encryption.



  32. Blue d20 on November 13, 2019 at 6:52 pm

    The first quantum computer was made one week ago from when I’m writing this.



  33. Edvin Rushitaj on November 13, 2019 at 6:54 pm

    I watched the whole video and the only thing i got is: one over pee 🙁
    Why im even here



  34. Satwik Mudgal on November 13, 2019 at 6:56 pm

    Nine:-i…i……am not crappy

    *Nine has left the conversation*



  35. Ulrich Erasmus on November 13, 2019 at 6:56 pm

    You’re daily dose of "So, you thought you were smart?" Also, you were over simplifying?? I’ll have to watch it a few times.



  36. Mike Mestnik on November 13, 2019 at 7:00 pm

    This video ignores ECC, that everyone is switching to!



  37. seasong on November 13, 2019 at 7:00 pm

    can you talk about quantum ray tracing?



  38. Waluigi is the king A. Smith on November 13, 2019 at 7:01 pm

    Hey a one time pad still works. The key just needs to be as big as the data



  39. MrDontuknowme on November 13, 2019 at 7:01 pm

    Lost me 🤷🏾‍♂️



  40. Aidenne Campbell on November 13, 2019 at 7:02 pm

    I’m lost…



  41. Sarvashaktimaan on November 13, 2019 at 7:06 pm

    Your channel both encourages me and discourages me from studying physics in the future.



  42. Pat John on November 13, 2019 at 7:07 pm

    Except you’ll have quantum encryption too so they will cancel each other oth



  43. zelzmiy on November 13, 2019 at 7:07 pm

    Yes, i understand this



  44. Saschahi on November 13, 2019 at 7:07 pm

    Got to 12:50 before I gave up even listening and just started reading comments



  45. Nick Ergodos on November 13, 2019 at 7:09 pm

    So the quantum computers with quantum supremacy is here now



  46. Mattia_98 on November 13, 2019 at 7:10 pm

    2048bit RSA encryption isn’t even that good. For RSA 4096bit is standard and RSA is obsolete anyways..



  47. Mohammad M on November 13, 2019 at 7:10 pm

    Welcome minutephysics fans. Today you just took a semesters worth of discrete mathematics for computer science.



  48. Vishvraj Chauahan on November 13, 2019 at 7:11 pm

    C’mon guys I am 14 and still understand this



  49. Zenax on November 13, 2019 at 7:12 pm

    Who else didn’t understand and felt lost but watched cause it was interesting?



  50. Xiellion on November 13, 2019 at 7:12 pm

    Just use a key file for two factor authentication, literally unbreakable unless you know what that key file is