News, news analysis, and commentary on the latest trends in cybersecurity technology.

YouTuber minutephysics explains how Shor's algorithm builds on existing formulae like Euclid's algorithm and Fourier transforms to leverage quantum superpositioning and break encryption.

The rise of quantum computing and its implications for current encryption standards are well known. But why exactly should quantum computers be especially adept at breaking encryption? The answer is a nifty bit of mathematical juggling called Shor's algorithm. The question that still leaves is: What is it that this algorithm does that causes quantum computers to be so much better at cracking encryption? In this video, YouTuber minutephysics explains it in his traditional whiteboard cartoon style.

"Quantum computation has the potential to make it super, super easy to access encrypted data — like having a lightsaber you can use to cut through any lock or barrier, no matter how strong," minutephysics says. "Shor's algorithm is that lightsaber."

According to the video, Shor's algorithm works off the understanding that for any pair of numbers, eventually multiplying one of them by itself will reach a factor of the other number plus or minus 1. Thus you take a guess at the first number and factor it out, adding and subtracting 1, until you arrive at the second number. That would unlock the encryption (specifically RSA here, but it works on some other types) because we would then have both factors.

One reason why this seemingly simple process relies on the development of powerful quantum computers is that finding the correct power to multiply the first number by in order to find a factor of the second number (N) ± 1 takes an enormous amount of tries. The encryption key is quite a long number and thus the power could be anything from 1 to millions. But brute force is not why quantum computers work so well here.

The Superpowers of Superpositions

Briefly, thanks to quantum superpositioning, a quantum computer can calculate many answers for a single input. However, the video says that you only get one answer output at a time, with probabilities attached. To solve that issue, the calculation is set up so that wrong answers interfere with each other so that only the correct answer (or at least a good guess) is likely to be output. That calculation, which focuses on finding the right power p, is Shor's algorithm.

It's all extremely mathemagical, involving an assist from Euclid's algorithm, as well as a quantum Fourier transform that turns a series of superpositions of superpositions into sine waves that either constructively (add to each other) or destructively interfere — i.e., cancel each other out. The video says that, essentially, you can rig it so that only 1/p is saved, with all the other answers destructively interfered out of contention. Once you're there, it's a walk in the park to find p, which makes finding the two encryption factors a whole lot easier. Watch the whole video for more details, and to maybe feel a little smarter.

By the way, Peter Shor is still thriving, and if you're interested in a deep dive on how he broke the Internet, here's another video where the man himself explains how he figured out his eponymous masterpiece.

About the Author(s)

Karen Spiegelman, Features Editor

Karen joined Dark Reading in January 2022 as features editor. She's been in tech editing since before the img tag was introduced, working for outlets such as the IEEE Computer Society, CNET Download.com, and TechTV. She lives in Los Angeles with her husband, son, and two cats. Find her on Mastodon.

Keep up with the latest cybersecurity threats, newly discovered vulnerabilities, data breach information, and emerging trends. Delivered daily or weekly right to your email inbox.

You May Also Like


More Insights