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

Question

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.

Answer 1

The question to answer is "Is N the product of P*Q?" I believe that the easiest way to understand Shor is to imagine two sine waves, one length P and one length Q. Assuming that P and Q are co-prime, then the question above can also be answered "At what point does the harmony of P overlapped with Q repeat itself?" And the answer can be determined quickly, based upon the simple observation that we can figure out the phase of each wave at any given point on the number line. (The phase, remember, is "how far along the pattern is this point?" and is often measured in degrees; 90 degrees = 1/4 rotation)

If we look at the point N then the phase of P and Q must be 0 if they are factors of N (or else there would be a remainder of the division N/Q or N/P). Shor just tests whether the phase of P == the phase of Q == 0 at point N. It turns out that phase estimation is pretty easy for quantum computers, so it's a good tool to build into a factoring machine. See http://www.wikipedia.org/wiki/Quantum_phase_estimation_algorithm for more information.