This story is over 5 years old.

Peter Shor Explains His Namesake Encryption-Crumbling Quantum Algorithm

The latest from 100 Second Science.
October 4, 2015, 3:30pm
Image: Nick Carter/Flickr

When people talk about the "cryptopocalypse," in which classical encryption methods are summarily rendered obsolete by quantum computing technology, they're usually talking about Shor's algorithm, whether or not they realize it. Quantum computing isn't magic, after all, and it's just as much a realm of computer scientists and algorithms as the technology we work with today. There are just some different rules.


Peter Shor figured out how to exploit those rules to find the prime factors of very large numbers. This is the computational task that stands between conventional RSA encryption and nothing at all. Given enough computing power, it's possible to find those prime factors, which will reveal the desired key. No computer is capable of this, nor will there ever be one using classical or non-quantum technology.

In the latest of Physics World's 100 Second Science series, Shor himself explains how this is supposed to work.