# 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
No, because it also solves discrete logarithm efficiently. $\:$ – Ricky Demer 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

## 1 Answer

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.

-
That's actually a really great way of explaining it. – Polynomial Oct 10 '12 at 7:31
The question to answer is "Of which P and Q at least 2 is N the product of?" rather than "Is N the product of P*Q?". For the later we have very efficient algorithms, polynomial in Log(N) on classical computers. – fgrieu Oct 10 '12 at 10:39