Season 17, Episode 1: Why Do Quantum Computers Break Cryptography

Hey StarTalkers! In Neil and Chuck’s discussion with Professor John Martinis in the first episode of Season 17, they touch briefly on the issue of cryptography in the coming age of quantum computers.

An Interview with the Winner of the 2025 Nobel Prize in Physics, John Martinis

Professor Martinis gives a brief explanation of the problem in this clip: a common form of encryption called RSA will be made obsolete by a quantum computing algorithm called Shor’s algorithm. In a way, physicists around the world are working hard on something that could put your data at risk.

But the scary predictions miss some important detail. So let’s look at what Shor’s algorithm actually does, and how things are likely to change in future.

Why Will Quantum Computing Break RSA Encryption?

RSA encryption uses two large prime factors of a very big number. The paper it was proposed in recommends multiplying two 100-digit prime numbers to end up with a 200 digit key. This 200 digit number is public, but the prime factors are crucial secret information.

The encryption system works because finding prime factors of very large numbers is really difficult. It would have taken billions of years to crack when it was proposed in the late 70s, but still a year or two with modern technology.

But in 1997, Peter Shor proved that quantum computers could make short work of the task. Quantum computers can use a superposition of different possibilities – rather than just one at a time – to search more efficiently.

Shor’s algorithm uses the repetition inherent in modular arithmetic alongside quantum Fourier transformations to find the prime factors. Think of it this way: each original prime p and q is the wavelength of a wave, and the points n where they are completely in phase are the ones that can be factored into p and q.

So Should We Be Worried?

The good news is that quantum-proof cryptography is basically ready-to-go.

It’s also pretty difficult to make a quantum computer that can actually handle Shor’s algorithm. There is progress, but nothing can break current systems yet.  

So physicists really are working on something that will put your data at risk, but luckily, security experts are working even faster.