Why is shor's algorithm only effective in quantum computer?

Question

I'm trying to learn about quantum computing and came across Shor's algorithm to find prime factors of a number. I understand the math behind shor's algorithm but can't understand why it can't be implemented in a classical computer as it just seems like a mathematical formula.

Answer 1

In short, Shor's algorithm to factor N consists of:

1. Make a (bad) random guess g of a number that could have a common factor with N
2. Find an even number p such that g^p = m*N+1
3. Then g^(p/2)±1 is a much better guess

Step 1 and 3 can be efficiently done on a classical computer using Euclid's algorithm. But for the second step, you need a quantum computer to be efficient (a classical computer would need to try every power p, one by one. So yes, it's just math, but this is not faster than any other classical factorizing algorithm).

Shor's algorithm exploits the superposition principle of states used by qbits. This gives the possibility to evolve a function of the superposition all at once. Practically this means it can try all powers of p simultaneously.