A quantum computer in the next decade could crack the encryption our society relies on using Shor's Algorithm. Head to https://brilliant.org/veritasium to start your free 30day trial, and the first 200 people get 20% off an annual premium subscription.

▀▀▀
A huge thank you to those who helped us understand this complex field and ensure we told this story accurately Dr. Lorenz Panny, Prof. Serge Fehr, Dr. Dustin Moody, Prof. Benne de Weger, Prof. Tanja Lange, PhD candidate Jelle Vos, Gorjan Alagic, and Jack Hidary.

A huge thanks to those who helped us with the math behind Shor’s algorithm Prof. David Elkouss, Javier Pagan Lacambra, Marc Serra Peralta, and Daniel Bedialauneta Rodriguez.

▀▀▀
References:
Joseph, D., et al. (2022). Transitioning organizations to postquantum cryptography. Nature, 605(7909), 237243. https://ve42.co/Joseph2022

Bernstein, D. J., & Lange, T. (2017). Postquantum cryptography. Nature, 549(7671), 188194. https://ve42.co/Bernstein2017

An Insight, An Idea with Sundar Pichai Quantum Computing, Wold Economic Forum via YouTube https://ve42.co/QCWEFyt

Migrating to PostQuantum Cryptography, The White House https://ve42.co/PQCWhiteHouse

Kotas, W. A. (2000). A brief history of cryptography. University of Tennessee https://ve42.co/Kotas2000

Hellman, M. (1976). New directions in cryptography. IEEE transactions on Information Theory, 22(6), 644654. https://ve42.co/Hellman1976

Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and publickey cryptosystems. Communications of the ACM, 21(2), 120126. https://ve42.co/Rivest1978

Kak, A. (2023). Lecture 12: PublicKey Cryptography and the RSA Algorithm https://ve42.co/Kak2023

Calderbank, M. (2007). The RSA Cryptosystem: History, Algorithm, Primes. University of Chicago. https://ve42.co/Calderbank2007

Cryptographic Key Length Recommendation, Keylength https://ve42.co/KeyLength

Coppersmith, D. (2002). An approximate Fourier transform useful in quantum factoring. arXiv preprint quantph/0201067. https://ve42.co/Coppersmith2002

Quantum Fourier Transform, Qiskit https://ve42.co/Qiskit

Shor, P. W. (1994, November). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science (pp. 124134). IEEE. https://ve42.co/Shor1994

Shor’s algorithm, Wikipedia https://ve42.co/ShorWiki

Euler’s totient function, Wikipedia https://ve42.co/EulerWiki

Asfaw, A. (2020). Shor’s Algorithm Lecture Series, Qiskit Summer School https://ve42.co/ShorYT

How Quantum Computers Break Encryption, minutephysics via YouTube https://ve42.co/PQCmpyt

Breaking RSA Encryption an Update on the StateoftheArt, QuintessenceLabs https://ve42.co/QuintessenceLabs

O'Gorman, J., & Campbell, E. T. (2017). Quantum computation with realistic magicstate factories. Physical Review A, 95(3), 032338. https://ve42.co/OGorman2017

Gidney, C., & Ekerå, M. (2021). How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5, 433. https://ve42.co/Gidney2021

2021 Quantum Threat Timeline Report, Global Risk Institute https://ve42.co/QuantumRisk

The IBM Quantum Development Roadmap, IBM https://ve42.co/IBMQC

PostQuantum Cryptography, Computer Security Resource Center (NIST) https://ve42.co/CSRCPQC

Alagic, G., et al. (2022). Status report on the third round of the NIST postquantum cryptography standardization process. US Department of Commerce, NIST. https://ve42.co/Alagic2022

Thijs, L. (2015). Lattice cryptography and lattice cryptanalysis https://ve42.co/Thijs2015

▀▀▀
Special thanks to our Patreon supporters:
Tj Steyn, Meg Noah, Bernard McGee, KeyWestr, Elliot Miller, Jerome Barakos, M.D., Amadeo Bee, TTST, Balkrishna Heroor, Chris LaClair, John H. Austin, Jr., Eric Sexton, john kiehl, Anton Ragin, Diffbot, Gnare, Dave Kircher, Burt Humburg, Blake Byers, Evgeny Skvortsov, Meekay, Bill Linder, Paul Peijzel, Josh Hibschman, Mac Malkawi, Juan Benet, Ubiquity Ventures, Richard Sundvall, Lee Redden, Stephen Wilcox, Marinus Kuivenhoven, Michael Krugman, Cy 'kkm' K'Nelson, Sam Lutfi.

▀▀▀
Written by Casper Mebius & Derek Muller
Edited by Trenton Oliver
Filmed by Raquel Nuno
Animated by Ivy Tello & Mike Radjabov
Additional video/photos supplied by Getty Images & Pond5
Music from Epidemic Sound & Jonny Hyman
Produced by Derek Muller, Petr Lebedev, & Emily Zhang