How does Shor’s algorithm speed up factoring large numbers?

Question

I try and remind myself a few times a year, but clearly it never actually clicks.

In: Mathematics

Answer 1

Shor’s algorithm is a quantum algorithm that quickly solves the order finding problem which is basically equivalent to factoring a large number.

The order finding problem is this:

Given your large number N and a smaller number x that is coprime (meaning the greatest common divisor is 1), find the smallest r such that x^r divided by N leaves remainder 1 or x^r (mod N) = 1.

Shor’s algorithm says you can use devise a quantum algorithm to quickly calculate this r:

If you set up a superposition across all possible values from 1 up to N of (1, x¹ mod N), (2, x² mod N), … where x mod N means the remainder of X when divided by N, then this superposition can be collapsed by an operator (the quantum Fourier transform) operator to have only non zero values for multiples of r.