# 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. $\:$ – Ricky Demer Oct 6 '12 at 10:12
@RickyDemer Maybe, but isn't the whole scary part that it can factor semiprimes in polynomial time, thus rendering a good portion of our current asymmetric ciphers broken? – Polynomial Oct 6 '12 at 10:25
No, because it also solves discrete logarithm efficiently. $\:$ – Ricky Demer Oct 7 '12 at 20:38