# In layman's terms, how does Shor's algorithm work?

I've just been reading up on Shor's algorithm, and I find it both fascinating and baffling. I don't understand much about it, other than that it can factor semiprimes in polynomial time.

Could someone explain how it works in layman's terms and why it is reliant on quantum computing?

Keep in mind that while I understand quantum computing basics (i.e., it uses photons instead of electrons, and bits are replaced with qubits that can be 0, 1, or a superposition of both), I don't know anything in-depth about it. I know it's supposedly super-fast compared to classical computing mechanisms.

• Take a look at scottaaronson.com/blog/?p=208 Commented Oct 3, 2012 at 15:56
• I'm not qualified to provide an answer, but the following article may be what you are seeking: arstechnica.com/security/2012/09/… Commented Oct 4, 2012 at 12:28
• I think Shor's algorithm would work even if its input wasn't a semiprime. $\:$
– user991
Commented Oct 6, 2012 at 10:12
• No, because it also solves discrete logarithm efficiently. $\:$
– user991
Commented Oct 7, 2012 at 20:38
• My take on it is that Shor's algorithm evaluates the period of $a^x \pmod{n}$ where $\gcd{(a, n)} = 1$. This is not efficient on a classical computer, but when run on a quantum computer, a miracle occurs and we get a congruence of squares with probability $0.5$ in polynomial time. The miracle part is, I guess, what you're asking.. but that requires physics and maths knowledge that's beyond me. Commented Oct 10, 2012 at 5:53