Break RSA encryption with this one weird trick

Cryptographers HATE it!

Too much math; didn’t read — Shor’s algorithm doesn’t brute force the entire key by trying factors until it finds one, but instead uses the quantum computer to find the period of a function which contains the RSA key and classically compute the greatest common divisor.

RSA encryption is strong because factoring is a one-way problem. It’s very easy to multiply two primes together, but very difficult to find prime factors of a large number. That’s what the technology relies on. And the simplicity of RSA encryption made it very popular.

However, one technology can render RSA useless.

(Hint: it’s a quantum computer)

Shor’s algorithm can crack RSA. But how does it really work?

It’s not about trying all prime factor possibilities simultaneously.

In (relatively) simple language:

We can crack RSA if we have a fast way of finding the period of a known periodic function f(x) = m^x (mod N)

Five Steps of Shor

So how does Shor’s algorithm work? In the five steps of Shor’s algorithm, only ONE requires the use of a quantum…