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 really understand much about it, other than that it can factor semiprimes in polynomial time.

Could someone provide a layman's terms explanation of how it works, and why it is reliant on quantum computing?

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

• Take a look at scottaaronson.com/blog/?p=208 – Huck Bennett Oct 3 '12 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/… – ericball Oct 4 '12 at 12:28
• I think Shor's algorithm would work even if its input wasn't a semiprime. $\:$ – user991 Oct 6 '12 at 10:12
• No, because it also solves discrete logarithm efficiently. $\:$ – user991 Oct 7 '12 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. – Thomas Oct 10 '12 at 5:53